トロミノゲーム

マス数が偶数なら codex は直前の赤マスを $180$ 度回転したマスに応手する。不動マスがないので常に合法で、最後には回転が赤と青の配置を一対一に対応させる。得点が等しくなり codex が勝つ。 一辺が $1$ なら $(1,2),(3,4),\ldots$ を組にし、奇数長では末尾を単独にする。codex は直前のマスの相方が未着色ならそこを選び、そうでなければ任意の未着色マスを選ぶ。各組には必ず青が入り、連続三マスは完全な組を含む。赤のトロミノはできないので codex が勝つ。 それ以外では両辺が $3$ 以上の奇数である。coxld は最初に中央を取り、その後は $180$ 度回転で応手する。中央を含まない赤と青の配置は対応する。中央の上下左右では向かい合うマスが異色なので、赤の二マスは中央から見て互いに垂直な方向にある。中央と合わせて赤い L 字形を作り、coxld が勝つ。 サブタスク 1 は三進状態とミニマックスを使う。配置数を $K$ とすると時間 $O(3^{RC}(RC+K))$、空間 $O(3^{RC}+K)$。全体解は一ケースあたり時間・追加空間とも $O(1)$。配置数は高々 $6RC\le6\cdot10^6$ で、面積の積は 64 ビットで計算する。 Solution written by GPT6.1