AtCoder Grand Contest 033

更新日時:

AtCoder Grand Contest 033

ソースコード

解法のメモ

A - Darker and Darker

普通に BFS をすればよろしい。

B - LRUD Game

$0$-indexed とする。操作を逆順に見ていく。時系列を逆順にする。

定義: 領域 $D$ がその時の 安全な領域 であるとは、任意の点 $p \in D$ に対し、任意の高橋君の操作に対し、青木君の操作が存在し、その点にある駒が落ちないようにゲームを終了でき、任意の $p \not \in D$ に対してはそうでないことを指す。

初期状態は $D = H \times W = [0, H - 1] \times [0, W - 1]$ である。

青木君の方は、 $D$ を拡張することができる。例えば 'L' が来ると、 $D$ の右側のマスを $+1$ しても大丈夫なことがわかる。そのような駒があったとしたら、青木君はその 'L' で左に戻せばそれまでの安全な領域に駒を動かすことができるからだ。ただし全領域からははみ出さないようにする必要がある。

高橋君の方は、 $D$ を狭めることができる。例えば 'L' が来ると、 $D$ の左側のマスを $-1$ することがわかる。そのような駒があったとしたら、高橋君はその 'L' で左に動かせばそれまでの安全な領域の外に駒を動かすことができるからだ。

以上の操作と初期状態を踏まえれば、常に $D = [up, down] \times [left, right]$ の形をしている。愚直にシミュレーションできる。答えが "YES" であるための必要十分条件は常に $D \neq \emptyset$ であること、かつ、最終局面で $(s_c, s_r) \in D$ であることである。

ポイント

嘘解法が通されたらしい。

C - Removing Coins

解答

木の直径を $L$ とすると、 $L \% 3 = 1$ のとき "Second", そうでないとき "First" である。

解答の正当化

操作によってコインが置かれなかった頂点は、木から取り除くものとして良い。するとこの操作は、

  • 最初に選ぶ頂点が根である場合:その根以外の根を $1$ 段階取り除く
  • 最初に選ぶ頂点が根以外である場合:全ての根を $1$ 段階取り除く

ことに相当する。

命題 1:木の直径 $L$ は、 1 回の操作により、 $L - 1$ または $L - 2$ になる。ただし悲負の数を考えるものとする。

証明:木の直径を構成する任意の頂点を指定して操作すると、直径は $L - 1$ になる。そうでなければ $L - 2$ になる。

命題 2:木の直径を $L$ とする。このとき Grundy 数 $G$ は、以下で与えられる。 \[ G = G(L) = \begin{cases} 0 & L \% 3 = 1, \\\ 1 & L \% 3 = 0, \\\ 2 & L \% 3 = 3. \end{cases} \] すなわち、 $1, 0, 2, 1, 0, 2, \dots$ となる。

証明: $L$ についての数学的帰納法による。 $L = 0$ のとき、どのように操作しても木は $\emptyset$ になるので、後手は負ける。よって Grundy 数は $1$ である。 $L = 1$ のとき、操作により $L = 0$ の木にしかならないので、 Grundy 数は $0$ である。 $L \geq 2$ とし、 $L - 1$, $L - 2$ での成立を仮定する。このとき、操作により直径が $L - 1$ の木、または、直径が $L - 2$ の木にしかならない。よって Grundy 数の定義により、次式が成立する。 \[ G = \min \{ n \in \mathbb{N} \mid n \neq G(L - 1) \land n \neq G(L - 2) \}. \] 帰納法の仮定に基づき場合分けをすることにより、命題 2 が示される。

木の直径 $L$ は DFS を 2 回することにより $O(N)$ で求まる。 $L \% 3 = 1$ のとき、答えは "Second" であり、そうでなければ "First" である。

ポイント

直径に気づけば、解けたと思う。もう少し大きい例で試してみるべきだった。

D - Complexity

ポイント

E - Go around a Circle

ポイント

F - Adding Edges

ポイント

その他