コンテンツにスキップ

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

サイト
SamCoding
コンテスト
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 を書かなくても質問はジャッジに届きます。