Codeforces Round #551 E. Serval and Snake

Problem - E - Codeforces

これ結構好き。

問題概要

インタラクティブ問題である。

$n \times n$ のグリッドがあり、グリッド内に蛇がいる。蛇の両端は異なるマスにあり、胴体は隣り合うマスを渡って両端を繋ぐパスとして表現される。

以下のクエリを2019回投げることが出来る。蛇の両端がどこのマスにあるか特定せよ。

グリッドの部分長方形をクエリとして指定する。返答として、蛇の胴体がその長方形の辺を横切る合計回数を得ることが出来る。

制約

$2 \le n \le 1000$

解法

胴体のパターン数は膨大にあり、胴体の形を考えようとすると破滅します。両端だけ求めれば良いので、これを直接求めます。

もし指定した長方形に蛇の両端のうち片方だけが入っていた場合、胴体が長方形の辺を横切る回数は奇数になります。入っていない場合と両方入っている場合は偶数になります。ここに着目します。

まず両端の行座標を特定します。以下の図のように、クエリの上・左・右の辺をグリッドの端に固定し、下の辺を1つずつ増やしていきます。こうすると、もし両端が同じ行にない場合は2つの行座標を特定することができます。これらの座標を $X_{1}, X_{2}$ としておきます。必要なクエリ数は $N$ 回です。（最後の1回は要らないので、 $N-1$ 回でも十分です）

f:id:betrue12:20190414140330p:plain

同様のことを列に対しても行います。もし両端が同じ列にない場合は2つの列座標を特定することができます。これらの座標を $Y_{1}, Y_{2}$ としておきます。やはり必要なクエリ数は $N$ 回です。

ここで両端は同じ座標にはないので、行と列のうち少なくとも片方は特定できていることになります。ここまでのクエリ数は $2N$ 回です。

どちらの座標も異なっていた場合

行と列どちらの座標も異なっていた場合、行座標が $X_{1}, X_{2}$ であり列座標が $Y_{1}, Y_{2}$ であると特定できています。あとはどっちとどっちが対応するか決まれば終わりです。

$(X_{1}, Y_{1})$ 1マスだけからなる長方形をクエリとして投げ、この返答が奇数であれば $(X_{1}, Y_{1}), (X_{2}, Y_{2})$ が答えです。返答が偶数であれば逆の組み合わせが答えです。

どちらかの座標が同じだった場合

行座標は異なっていて特定できたが、列座標が同じであるため特定できなかった場合を考えます。逆も同様です。

この場合、特定できた片方の行だけを見ると「どこかに1つだけ蛇の端点がある」状態になっています。そのため以下の図のように、左辺を端に固定して以下のように右辺を変えながらクエリを投げると、返答が奇数になる境目が蛇の端点の列座標です。これは2分探索できて $\lceil \log_{2} N \rceil$ 回のクエリで特定できます。