SamCoding Round 7 (Div. 2) H - Mysterious Valley
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- H - Mysterious Valley(常設版)
個の地点が一列に並び、それぞれの高さはすべて異なります。両隣より低い地点(谷)を 1 つ見つけるインタラクティブ問題です。端の地点では、外側に無限に高い山があるとみなします。
? i と質問すると地点 の高さが返ってきます。質問は 回までで、 は最大 です。
二分探索で谷を探します。
端を先に調べる
Section titled “端を先に調べる”まず端を調べます。
- なら、地点 が谷です。
- なら、地点 が谷です。
どちらでもなければ、(左端では下り)かつ (右端では上り)です。
「下り」と「上り」の間を狭める
Section titled “「下り」と「上り」の間を狭める”を「(下り)」、 を「(上り)」を満たす位置として、、 から始めます。
と の真ん中 で と を比べ、上りなら 、下りなら とします。こうすれば、 では下り、 では上り、という状態がずっと保たれます。
になったら、 かつ なので、地点 が谷です。
は 1 回ごとにほぼ半分になるので、繰り返しは 回以下です。1 回の繰り返しで質問するのは と の 2 つなので、最初の 4 回と合わせて 回以下に収まります。
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 = 1r = N - 1while l + 1 < r: m = (l + r) // 2 if q(m) < q(m + 1): r = m else: l = mprint("!", r)q(x) は地点 の高さを質問する関数で、同じ地点を 2 回質問しないように結果を d に覚えています。
問題文では出力のたびにフラッシュするように書かれていますが、Python の input() は読み込む前に標準出力をフラッシュするので、flush を書かなくても質問はジャッジに届きます。