コンテンツにスキップ

ShareOJ - Smallest and Largest Subarray

サイト
ShareOJ
問題
Smallest and Largest Subarray

長さ NN の隠された整数列 AA について、連続部分列のうち辞書順で最小のものと最大のものを 1 つずつ答えるインタラクティブ問題です。

? l r l' r' と質問すると、(Al,…,Ar)(A_l, \dots, A_r) が (Al′,…,Ar′)(A_{l'}, \dots, A_{r'}) より辞書順で真に小さいかどうかが返ってきます。N=1000N = 1000 で、質問は Q=1500Q = 1500 回までです。

連続部分列 (Ai,…,Aj)(A_i, \dots, A_j) について、次のことがいえます。

  • 先頭の 1 要素 (Ai)(A_i) はこの列の接頭辞なので、(Ai)(A_i) 以下です。したがって、最小のものは長さ 1 の列 (Ai)(A_i) にとれます。
  • この列は接尾辞 (Ai,…,AN)(A_i, \dots, A_N) の接頭辞なので、接尾辞以下です。したがって、最大のものは接尾辞にとれます。

そこで、接尾辞どうしを比べることにします。長さの違う接尾辞が等しくなることはないので、NN 個の接尾辞はすべて大小が決まります。

  • 最大の接尾辞 (Ar,…,AN)(A_r, \dots, A_N) が、そのまま最大の連続部分列です。
  • 最小の接尾辞 (Al,…,AN)(A_l, \dots, A_N) の先頭 AlA_l は、AA の最小値です。先頭の値がより小さい接尾辞があれば、そちらのほうが小さいからです。よって (Al)(A_l) が最小の連続部分列です。

あとは、NN 個の接尾辞の最小と最大を、比較 15001500 回以内で求めればよいです。

最小と最大を別々に求めると 2(N−1)=19982(N - 1) = 1998 回かかり、間に合いません。

そこで、接尾辞を 2 つずつ組にします。まず組の中で比べ、小さいほうだけを今の最小の候補と、大きいほうだけを今の最大の候補と比べます。1 組あたりの比較は 3 回です。

最初の組は比べるだけで最小と最大の候補になるので 1 回です。N=1000N = 1000 は偶数なので組はちょうど 500500 個できて、比較は全部で 1+3×499=14981 + 3 \times 499 = 1498 回です。15001500 回に収まります。

これは 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 = 2
else:
l = 2
r = 1
for 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 = b
print("!", l, l, r, N)

接尾辞 (Ai,…,AN)(A_i, \dots, A_N) を i N で表しています。l は最小の接尾辞の、r は最大の接尾辞の開始位置の候補です。各組では、小さいほうを a、大きいほうを b としています。