Lを取れ

L 字形は、ある列の両方のマスと、その隣の列の $1$ マスを取る。したがって必ず空の列ができ、左右は互いに影響しない独立したゲームになる。

空の列で区切った各区間では、端の列だけが $1$ マスになり得て、内部の列には常に $2$ マスが残る。この性質はどの手の後にも保たれる。

区間の残りマス数を $k$ とする。どの手も、大きさが $a$ と $k-3-a$ の二つの区間を残す。逆に、$0\le a\le k-3$ のすべての分割が可能である。マスを左の列から順に並べると、連続する $3$ マスは必ず一つの列の $2$ マスと隣の列の $1$ マスになる。先頭の $a$ マスの直後の $3$ マスを取ればよい。他の向きで取っても、新しい大きさの組は生じない。

よってグランディ数はマス数だけで決まる。これを $G(k)$ とすると、

$$G(0)=G(1)=G(2)=0$$

であり、$k\ge3$ について

$$G(k)=\operatorname{mex}\{G(a)\oplus G(k-3-a)\mid 0\le a\le k-3\}$$

となる。$\operatorname{mex}$ は集合に含まれない最小の非負整数、$\oplus$ はビット XOR である。

最初は $2N$ マスの区間が一つある。$G(2N)\ne0$ なら YES、そうでなければ NO を出力する。

入力中の $N$ の最大値を $M$ とする。$G(2M)$ までの前計算は $O(M^2)$ 時間、$$ 空間で行える。その後は各ケースを 時間で処理でき、全体の時間計算量は 、入力を含む空間計算量は である。

サブタスク 1 は $N\le10$ である。$2N$ マスの状態をビットマスクで表し、合法な L をすべて試すメモ化探索を行う。同じ $N$ の答えを再利用すれば、$K=\max N\le10$ に対し時間は 、空間は 以下となる。サブタスク 2 では上記のグランディ数を使う。

Solution written by GPT