AtCoder Beginner Contest 299, D : Find by Query

問題文

　https://atcoder.jp/contests/abc299/tasks/abc299_d

問題概要

　長さ $N$ の秘密の列 $S = S_1 S_2 \dots S_N$ があり，$S_1 = 0$ かつ $S_N = 1$ かつ $S_i \in \{ 0, 1 \}$ である．
　$S_i$ を尋ねる操作を 20 回まで行える．$S_i \neq S_{ i + 1 }$ となる $i$ をひとつ求めよ．

制約

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

解法

　順序対 $( l, r )$ であって，以下の条件を満たすものを考えます．

• $l < r$
• $S_l = 0$
• $S_r = 1$

これらの条件に加えて

• $l + 1 = r$

を満たすものを見つけることができれば，そのときの $l$ が答えになります．
　前者の条件を満たすものとして，$( l, r ) = ( 1, N )$ があります．
　前者の条件を満たす順序対 $( l, r )$ に対して，$m = \frac { l + r } 2$ とすると，$S_m $ の値によって

• $S_m = 0$ のとき $( m, r )$ は前者の条件を満たす
• $S_m = 1$ のとき $( l, m )$ は前者の条件を満たす

ということが言えます．この場合分けに従って順序対を更新する操作をすると，$r - l$ を半分程度にすることができます．これを $( l, r ) = ( 1, N )$ から始めて $r - l = 1$ になるまで繰り返せばよいです．半分にする操作で $1$ にする回数なので，$\log{ ( N - 1 ) } \leq \log N \leq 20$ 回の操作で達成できます．

コード

namespace io
{
	int query( const int i )
	{
		cout << "? " << i + 1 << endl;
		IN( int, res );
		return res;
	}

	void answer( const int i )
	{
		cout << "! " << i + 1 << endl;
		return;
	}
}

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N );

	int lb = 0, ub = N - 1;
	while ( lb + 1 < ub )
	{
		const int mid = ( lb + ub ) / 2;
		( io::query( mid ) ? ub : lb ) = mid;
	}

	io::answer( lb );

	return 0;
}