Kazun の競プロ記録

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

AtCoder Beginner Contest 269 E問題 Last Rook

AtCoder ABC269 ABC E問題 500 pts インタラクティブ

問題

提出解答

問題の概要

インタラクティブ問題

$N$ 行 $N$ 列のマスからなるチェス盤と $N$ 個のルークがある.

このうち, $(N-1)$ 個のルークが以下を満たすように置かれている.

どの行にも2個以上のルークが置かれていない.
どの列にも2個以上のルークが置かれていない.

このとき, 残りの1個のルークを上記の条件を満たすように置きたい.

以下の形式の質問を高々 $20$ 回行うことにより, 条件を満たすようにルークを置くことが可能なマスを1つ求めよ.

$1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$ を満たす整数の組 $(A,B,C,D)$ を用いて, マス $A \leq i \leq B, C \leq j \leq D$ を満たすマス $(i,j)$ に存在するルークの数を聞く.

制約

$2 \leq N \leq 10^3$

解法

まず, 可能なマスはただ1通りであることに留意する. そして, 行と列を独立に行い, マスを特定する方針をとる.

行について議論する. $1 \leq i \leq N$ となる整数 $i$ について, $R(i)$ を次のようにする.

$R(i):=i-$ ( $1$ 行目から $i$ 行目に存在するルークの数)

この $i=1,2, \dots, N$ について, 以下は同値になる.

$R(i) \geq 1$
$1,2, \dots, i$ 行目のうち, ルークが1個も置かれていない列が存在する.

可能なマス目の一意性から, $R(i) \geq 1$ を満たす最小の整数を $I$ とすると, $I$ 行目がルークが1個も置かれていない列である.

そして, $R(i)$ は単調増加である. よって, $I$ は二分探索によって求めることができる. また, $1,2, \dots, i$ 行目に存在するルークの数は $(A,B,C,D)=(1,i,1,N)$ の形式で質問できる.

二分探索における処理の回数は $1000 \leq 2^{10}=1024$ であるから, $10$ 回以内で終わる.

これによって高々 $10$ 回の質問で $I$ を特定でき, 同様にして列 $J$ も高々 $10$ 回の質問で特定できる.

以上から, $(I,J)$ が答えであり, 合計 $20$ 回以内の質問で特定できた.