考察
同じwordは二度使えずN≤16なので、gameの履歴で将来に必要なのはused/remaining subsetと直前wordの末尾文字だけである。
有限のnormal-play gameなので、現在playerが相手の負け状態へ遷移できるなら勝ち、全遷移が相手の勝ちなら負けとなる。
採用する候補: remaining word subsetと要求される先頭文字を状態にしたbit DPで勝敗を小subsetから計算する。
wordの使用順序を2^N状態にまとめ、minimaxを通常の勝敗recurrenceで評価できる。
棄却する候補: 可能なshiritori列をgame treeとして重複なく全探索する。
同じsubset・末尾へ至る順序が多数あり、memo化なしではN!規模になる。
状態が勝ちである必要十分条件は、先頭文字が一致するremaining wordの中に、使用後の状態が負けとなるものが1つでもあること。
初手だけ要求文字がないため、各wordを初手に選んだ後の相手状態が負けかを全wordについて調べればよい。
dp[mask][c]をremaining set=mask、要求先頭文字cから手番playerが勝てるかとする。使用可能word iごとにdp[mask\{i}][last_i]がfalseならtrueとし、maskの小さい順に埋める。full maskから任意初手で勝てればFirst。
典型の発動条件
subset game DP
発動条件: 各要素を高々一度使う交互gameで、Nが20未満のとき。
remaining/used subsetと局所的な接続条件を状態にして勝敗をmemo化する。
normal-play勝敗recurrence
発動条件: 手がないplayerが負ける有限gameを解析するとき。
負け状態への遷移があれば勝ち、なければ負けとする。
問題固有の要素
文字列本体の内容は初字・末字以外gameの合法性に影響せず、履歴の最後も末尾1文字へ圧縮できる。
別の問題へ持ち帰る視点: 連結ルール付き列gameでは、次の合法手判定に必要なboundary情報だけを状態に残す。
正当性
未使用単語集合と要求される先頭文字が同じなら、過去の使用順によらず合法手は同じである。未使用数0の状態は負けであり、その他は合法手のいずれかで相手を負け状態へ送れる時に限って勝ちとなる。各手は未使用単語を一つ減らすので、このminimax式は集合サイズの帰納法で正しい。初手には要求文字がないので全単語を試し、その後の相手状態が負けとなる単語の存在を調べれば先手勝敗が決まる。
実装上の注意
- remaining mask方式なら遷移先は小さいmaskなので昇順、used mask方式なら逆向きになることを揃える。
- 初手を表すdummy文字を26文字に混ぜず、全wordからの遷移を別に評価する。
復習の核
- 手がないmaskを負けと置き、1語・2語の小例から『相手を負けへ送れる』recurrenceを逆算する。
計算量と制約
時間
O(N2ᴺ)、各maskで各wordの先頭文字状態だけを更新。
空間
O(26·2ᴺ)、remaining mask×要求文字。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 16; N is an integer.; S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.; S _ i\neq S _ j\ (1\leq i\lt j\leq N)
出典