ABC 278 F — Shiritori

考察

同じ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)

出典

分類・前提・執筆情報

掲載状態: 収録済み

Shiritori の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: ゲーム状態の勝敗とGrundy数

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: game状態・Grundy DP

    補助タグ: 部分集合・bitmask状態DP

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: ゲーム状態の勝敗とGrundy数

    • 後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。

    先に読む単元:

    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 有限DAGの得点差minimax、循環ゲームの距離評価、独立な数ゲームの加算。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題