コンテンツにスキップ

インタラクティブ

タグ「インタラクティブ」の記事 4 件

ShareOJ - Truth or Lie

11 以上 NN 以下の秘密の整数 xx を当てるインタラクティブ問題です。

? l r と質問すると、xx が ll 以上 rr 以下かどうかが 11(はい)か 00(いいえ)で返ってきます。ただし、ジャッジは嘘つきかもしれません。嘘つきの場合は、常に逆の答えを返します。質問は 2020 回までで、N≤105N \le 10^5 です。

? 1 N と質問します。xx は必ず 11 以上 NN 以下なので、本当の答えは「はい」です。したがって、11 が返ってくればジャッジは正直者、00 が返ってくれば嘘つきだとわかります。

嘘つきなら、これ以降の応答をすべて反転すれば本当の答えになります。

あとは、ふつうの二分探索で xx を求めます。xx がありうる範囲を [l,r][l, r] として、真ん中 mm で区切り、xx が [l,m][l, m] にあるかを質問します。あれば r=mr = m、なければ l=m+1l = m + 1 とします。

範囲の大きさは 1 回ごとに半分(切り上げ)になるので、⌈log⁡2105⌉=17\lceil \log_2 10^5 \rceil = 17 回で 11 つに決まります。最初の 1 回と合わせて 1818 回なので、2020 回に収まります。

Python
N = int(input())
l = 1
r = N
print("?", 1, N, flush=True)
x = (int(input())) ^ 1
while l < r:
m = (l + r) // 2
print("?", l, m, flush=True)
res = int(input())
if res ^ x:
r = m
else:
l = m + 1
print("!", l, flush=True)

変数 x は秘密の整数ではなく、ジャッジが嘘つきなら 11、正直者なら 00 になるフラグです。res ^ x で応答を反転し、本当の答えに直しています。

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 としています。

SamCoding Round 7 (Div. 2) J - Lying Guard

11 以上 NN 以下の秘密の数 TT を当てるインタラクティブ問題です(N≤1018N \le 10^{18})。? i と質問すると、TT と ii の大小関係が >、<、= のいずれかで返ってきます。

ただし、答える番人はゲーム全体を通して 1 回だけ 嘘をつくことがあります。= の答えが嘘のこともあります。質問は 190190 回までです。

ふつうの二分探索で、同じ質問を 3 回ずつして多数決をとります。

嘘はゲーム全体で高々 1 回なので、同じ質問への 3 回の答えのうち、少なくとも 2 回は本当です。そのため、多数決をとれば必ず正しい答えが得られます。正しい答えだけで二分探索を進めれば、ふつうの二分探索と同じく TT が求まります。

範囲 [l,r][l, r] の真ん中 mm を聞き、> なら l=m+1l = m + 1、< なら r=m−1r = m - 1、= ならそこで終わりにします。範囲の大きさは 1 回ごとに半分以下になるので、繰り返しは ⌊log⁡21018⌋+1=60\lfloor \log_2 10^{18} \rfloor + 1 = 60 回以下です。1 回につき 3 回質問するので、合計 180180 回以下で、上限の 190190 回に収まります。

Python
from collections import Counter
N = int(input())
l = 1
r = N
while l < r:
m = (l + r) // 2
c = Counter()
for _ in range(3):
print("?", m, flush=True)
c[input()] += 1
k = c.most_common()[0][0]
if k == "=":
l = r = m
elif k == ">":
l = m + 1
else:
r = m - 1
print("!", l, flush=True)

3 回の答えを Counter で数え、most_common()[0][0] で最も多い答えを取り出しています。= のときは l = r = m としてループを抜けます。

SamCoding Round 7 (Div. 2) H - Mysterious Valley

NN 個の地点が一列に並び、それぞれの高さはすべて異なります。両隣より低い地点(谷)を 1 つ見つけるインタラクティブ問題です。端の地点では、外側に無限に高い山があるとみなします。

? i と質問すると地点 ii の高さが返ってきます。質問は 130130 回までで、NN は最大 101810^{18} です。

二分探索で谷を探します。

まず端を調べます。

  • h1<h2h_1 < h_2 なら、地点 11 が谷です。
  • hN−1>hNh_{N-1} > h_N なら、地点 NN が谷です。

どちらでもなければ、h1>h2h_1 > h_2(左端では下り)かつ hN−1<hNh_{N-1} < h_N(右端では上り)です。

「下り」と「上り」の間を狭める

Section titled “「下り」と「上り」の間を狭める”

ll を「hl>hl+1h_l > h_{l+1}(下り)」、rr を「hr<hr+1h_r < h_{r+1}(上り)」を満たす位置として、l=1l = 1、r=N−1r = N - 1 から始めます。

ll と rr の真ん中 mm で hmh_m と hm+1h_{m+1} を比べ、上りなら r=mr = m、下りなら l=ml = m とします。こうすれば、ll では下り、rr では上り、という状態がずっと保たれます。

r=l+1r = l + 1 になったら、hl>hrh_l > h_r かつ hr<hr+1h_r < h_{r+1} なので、地点 rr が谷です。

r−lr - l は 1 回ごとにほぼ半分になるので、繰り返しは ⌈log⁡21018⌉=60\lceil \log_2 10^{18} \rceil = 60 回以下です。1 回の繰り返しで質問するのは hmh_m と hm+1h_{m+1} の 2 つなので、最初の 4 回と合わせて 4+2×60=1244 + 2 \times 60 = 124 回以下に収まります。

Python
d = {}
def q(x):
if x not in d:
print("?", x)
d[x] = int(input())
return d[x]
N = int(input())
if N == 1:
print("!", 1)
exit(0)
if q(1) < q(2):
print("!", 1)
exit(0)
if q(N - 1) > q(N):
print("!", N)
exit(0)
l = 1
r = N - 1
while l + 1 < r:
m = (l + r) // 2
if q(m) < q(m + 1):
r = m
else:
l = m
print("!", r)

q(x) は地点 xx の高さを質問する関数で、同じ地点を 2 回質問しないように結果を d に覚えています。

問題文では出力のたびにフラッシュするように書かれていますが、Python の input() は読み込む前に標準出力をフラッシュするので、flush を書かなくても質問はジャッジに届きます。