ShareOJ - Smallest and Largest Subarray
- サイト
- ShareOJ
- 問題
- Smallest and Largest Subarray
長さ の隠された整数列 について、連続部分列のうち辞書順で最小のものと最大のものを 1 つずつ答えるインタラクティブ問題です。
? l r l' r' と質問すると、 が より辞書順で真に小さいかどうかが返ってきます。 で、質問は 回までです。
答えの形を絞る
Section titled “答えの形を絞る”連続部分列 について、次のことがいえます。
- 先頭の 1 要素 はこの列の接頭辞なので、 以下です。したがって、最小のものは長さ 1 の列 にとれます。
- この列は接尾辞 の接頭辞なので、接尾辞以下です。したがって、最大のものは接尾辞にとれます。
そこで、接尾辞どうしを比べることにします。長さの違う接尾辞が等しくなることはないので、 個の接尾辞はすべて大小が決まります。
- 最大の接尾辞 が、そのまま最大の連続部分列です。
- 最小の接尾辞 の先頭 は、 の最小値です。先頭の値がより小さい接尾辞があれば、そちらのほうが小さいからです。よって が最小の連続部分列です。
あとは、 個の接尾辞の最小と最大を、比較 回以内で求めればよいです。
最小と最大を同時に求める
Section titled “最小と最大を同時に求める”最小と最大を別々に求めると 回かかり、間に合いません。
そこで、接尾辞を 2 つずつ組にします。まず組の中で比べ、小さいほうだけを今の最小の候補と、大きいほうだけを今の最大の候補と比べます。1 組あたりの比較は 3 回です。
最初の組は比べるだけで最小と最大の候補になるので 1 回です。 は偶数なので組はちょうど 個できて、比較は全部で 回です。 回に収まります。
これは C++ の std::minmax_element と同じ方法です。
Python
N, Q = map(int, input().split())print("?", 1, N, 2, N, flush=True)x = int(input())if x: l = 1 r = 2else: l = 2 r = 1for i in range(1, N // 2): print("?", 2 * i + 1, N, 2 * i + 2, N, flush=True) x = int(input()) if x: a = 2 * i + 1 b = 2 * i + 2 else: a = 2 * i + 2 b = 2 * i + 1 print("?", a, N, l, N, flush=True) x = int(input()) if x: l = a print("?", r, N, b, N, flush=True) x = int(input()) if x: r = bprint("!", l, l, r, N)接尾辞 を i N で表しています。l は最小の接尾辞の、r は最大の接尾辞の開始位置の候補です。各組では、小さいほうを a、大きいほうを b としています。