Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 299 D問題 Find by Query

AtCoder ABC ABC299 D問題 400 pts インタラクティブ

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

インタラクティブ問題

長さ $N$ の $0,1$ からなる整数列 $S$ がある. この $S$ は $S_0=0, S_N=1$ であることが保証されている.

次の形式の質問を $20$ 回以内行うことにより, $S_p=S_{p+1}, 1 \leq p \leq N-1$ であるような整数 $p$ を $1$ つ求めよ.

$1 \leq i \leq N$ を満たす整数 $i$ を $1$ つ選び, $S_i$ の値を聞く.

制約

$2 \leq N \leq 2 \times 10^5$

解法

(*) $1 \leq l \lt r \leq N$ に対して, $S_l=0, S_r=1$ ならば, $S_p \neq S_{p+1}, l \leq p \lt r$ を満たす整数 $p$ が存在する.

このことを利用して, 次のようにすると, $\left \lceil \log_2 N \right \rceil$ 回の質問でそのような $p$ を見つけることができる.

$l \gets 1, r \gets N$ とする. このとき, (*) の仮定は成立する.
である限り, として, の値を質問する.
- $S_m=0$ ならば, $l \gets m$ とする. このとき, (*) の仮定は満たされたままである.
- $S_m=1$ ならば, $r \gets m$ とする. このとき, (*) の仮定は満たされたままである.
$r-l=1$ のとき, (*) の仮定は満たされており, $l \leq p \lt r$ であるような整数は $p=l$ に限られる. よって, この $p$ が $S_p \neq S_{p+1}$ を満たす.

よって, $\left \lceil \log_2 2 \times 10^5 \right \rceil=18$ であるので, この方針によって, 条件を満たす $p$ を発見できる.