十分に賢いプレイヤーの戦略を確立しましょう．

\(N\) 人の帽子の色を RB 列で表します．

今まであなたが与えた情報と矛盾しない RB 列の集合 \(S\) を考えます． 各プレイヤーについて見えている帽子の数が違うので，\(S\) はプレイヤーごとに異なるように思えます． しかし \(S\) はあくまでも，”あなたが与えた情報”と矛盾しない RB 列の集合です． 別の言い方をすれば，プレイヤー \(1\) にとって可能性のある RB 列の集合が \(S\) です．

各プレイヤー \(i\) について，プレイヤー \(i\) にとって RB 列 \(x\) が矛盾していないことは，以下の \(2\) つの条件を満たすことと同値です．

• \(x \in S\)
• すべてのプレイヤー \(j\) (\(j<i\)) の帽子の色が \(x\) と一致する．

赤/青の帽子をかぶっているプレイヤーの人数を \(R,B\) とおきます． ラウンド\(1\) が始まる段階で \(S\) に含まれているのは，\(R\) 個の R と \(B\) 個の B からなる列全てです．

各ラウンドで何が起こるかを丁寧に観察しましょう． まず，あなたに質問されたプレイヤーは，以下のように考えます．

• プレイヤー \(i\) の思考: すべてのプレイヤー \(j\) (\(j<i\)) の帽子の色と \(S\) から，自分にとって矛盾しない RB 列の集合 \(T\) を決定する．もし，\(T\) 内のすべての RB 列において，プレイヤー \(i\) の帽子の色が同じであるなら，自分の帽子がその色だと確信できる．逆にそうでない場合は，自分の帽子の色はまだ確定できない．

次に，Yes と答えたプレイヤーをあなたが発表したあと，\(S\) は次のように変化します．

• 各 \(x \in S\) について考える．\(N\) 人の帽子の色が \(x\) だったと仮定したとき，このラウンドのあなたからの質問への返答がどうなるかをすべてのプレイヤーについて考える． もしこれが実際の返答(これはあなたの発表から知ることができる)と矛盾するなら，\(x\) を \(S\) から削除する．

これでゲームがどのように進行するかがわかりました． しかし，上記の戦略をそのまま実装すると，最低でも \(S\) のサイズに比例する計算量がかかり，この問題の制約ではとても間に合いません．

そこで，\(S\) に含まれる RB 列の特徴を考えます．

R を右，B を上と読み替えることで，RB 列をグリッド上のパス \((0,0)\to (R,B)\) とみなすことにします．

すると，\(S\) に対する更新はすべて，「ある点 \((x,y)\) を通るすべてのパスを \(S\) から削除せよ」という形で書けることがわかります． これを確認していきましょう．

まず，この性質を言い換えれば，\(S\) はグリッド上の禁止点集合で特徴づけられることになります． これをラウンド数に関する帰納法で示します．

ラウンド \(1\) の開始時に \(S\) がそのような形で書けることは明らかです．

今，あるラウンドの開始時に \(S\) が上記の形で記述できているとします． グリッド上の DP を行うことで，禁止点の集合を極大にしておきます． より具体的に述べれば，例えば \((10,11),(11,10)\) が禁止されている場合，\((10,10),(11,11)\) も禁止しておきます． こうすることで，点 \((x,y)\) が禁止点でない \(\iff\) \((x,y)\) を通る正当なパスが存在する，ということが保証できます．

各プレイヤーの思考をトレースしましょう． 自分から見える赤/青の帽子の個数を \(r,b\) すると，パスがある点 \((r,b)\) を通っていることが判明します． もし，\((r+1,b)\) が禁止されていれば，パスは \((r,b+1)\) に進むことが確定します． つまり，自分の帽子の色が青であると確定します． 赤についても同様の議論ができます． そして，\((r+1,b),(r,b+1)\) どちらも使用可能だった場合は，自分の帽子の色を決定できません． このように，\(S\) を禁止点集合で表すことによって，各プレイヤーの動きを知ることができます．

次に，あなたの発表のあとに \(S\) がどう変化するか見ます． 仮にパスが座標 \((x,y)\) を通っていたとします． ここで，プレイヤー \(x+y+1\) が直前の質問になんと返答していたかを参照します． 仮に返答が Yes だった場合，\((x+1,y),(x,y+1)\) のうちちょうど一方は禁止されているはずです． もしこれが成立しないならば，\((x,y)\) をパスが通ることはありえないとわかります． つまり，\((x,y)\) が禁止点として追加されます． プレイヤーの返答が No だった場合も同様の議論が行えます．

以上より，\(S\) をグリッド上の禁止点集合で特徴づけることで，\(1\) ラウンドの進行をシミュレートできることがわかりました． あとは，ラウンドを十分な回数繰り返し，禁止点集合がこれ以上変化しないと分かった段階で打ち切れば良いです．

必要なラウンド数を見積もってみます． 結論から言えば \(N\) ラウンドで十分です． 帰納法で示します． まず \(N=1\) のときは明らかです．

\(N>1\) のときを考えます． まず，プレイヤー \(2,3,\cdots,N\) の \(N-1\) 人は全員プレイヤー \(1\) の帽子が見えているため，これを除いて \(N-1\) 人でゲームをプレイしているとみなすことができます． 帰納法の仮定より，彼らの動きは \(N-1\) ラウンドで収束し，その後の動きには一切の情報がありません． つまり，プレイヤー \(1\) が最後に情報を得られるのがラウンド \(N-1\) なので，その動きに変化があるのは遅くともラウンド \(N\) です． これで示されました．

上記の議論をそのまま実装すれば，\(O(N^3)\) 解法が得られます．

実装例