ABC 433 G — Substring Game

考察

ゲーム中に作られる文字列は S の部分文字列であり、手番では末尾へ一文字追加してなお部分文字列である遷移を選ぶ。これは Suffix Automaton の初期状態からの遷移グラフそのものである。

採用する候補: S の Suffix Automaton を構築し、各状態をゲーム局面として DAG 上の勝敗を後退解析する。

状態・遷移数がともに O(|S|) で、同じ右文脈を持つ多数の部分文字列を一状態へ圧縮できる。

棄却する候補: 現在文字列そのものを set に持って全ての相異なる部分文字列を列挙する。

相異なる部分文字列は Θ(N^2) 個になり得る。

Suffix Automaton の各遷移は表す部分文字列へ一文字追加する操作に対応し、len が増えるため遷移グラフは DAG である。

出辺のない状態は手番プレイヤーの負け、負け状態へ移れる状態は勝ち、全遷移先が勝ちなら負けとなる。

S を一文字ずつ追加して Suffix Automaton を構築する。状態を len の降順に処理し、出辺先に losing が一つでもあれば winning、なければ losing とする。空文字列を表す初期状態の勝敗から Alice/Bob を答える。

典型の発動条件

Suffix Automaton

発動条件: 文字列の全相異なる部分文字列を、末尾への文字追加遷移を保った線形個の状態へ圧縮したいとき。

ゲーム局面の同値な right context を automaton の状態として共有する。

DAG ゲームの後退解析

発動条件: 各手で非巡回グラフの辺を進み、動けない側が負ける impartial game の勝敗を求めるとき。

長さ降順に、遷移先の勝敗から現在状態を決める。

問題固有の要素

部分文字列ゲームの将来の合法手は文字列の右文脈だけで決まり、Suffix Automaton がその Myhill–Nerode 型同値類を表す。

別の問題へ持ち帰る視点: 局面数が多い文字列ゲームは、合法な一文字拡張を受理する automaton 上のゲームへ圧縮できる。

正当性

SAMのstateは同じ右拡張languageを持つsubstringをまとめるのでゲームの合法次手集合も同じになる。遷移はlenを増やしcycleがない。出辺なしは負け、負けへ一手で行けるなら勝ち、全行先勝ちなら負けという有限DAGの帰納判定が最適playを表す。初期stateは空列からの全最初手を持つのでその値が全gameの勝敗。

実装上の注意

  • clone 状態を含む全状態を len 降順に処理する。terminal フラグではなく出辺の有無がゲーム終了条件である。

復習の核

  • automaton が suffix だけでなく全 substring の一文字拡張を表すこと、初期状態を空文字列局面として評価することを確認する。

計算量と制約

時間

O(|S|)の固定alphabet suffix automaton構築とlen順勝敗DP。

空間

O(|S|)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1\le T\le 10^5; T is an integer.; S is a string consisting of lowercase English letters with length between 1 and 2\times 10^5, inclusive.; The sum of the lengths of S over all test cases is at most 4\times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: Suffix Automatonで部分文字列集合を表す

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

    主タグ: Suffix Automaton

    補助タグ: game状態・Grundy DP

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

    学習の位置

    体系上の位置: Suffix Automatonで部分文字列集合を表す

    • endpos同値類を状態にし、suffix linkと必要なcloneを正しく作って全部分文字列の遷移を線形状態数で表せる。

    先に読む単元:

    • ゲーム状態の勝敗とGrundy数 — 状態遷移を設計できることを前提に、後続状態の勝敗やGrundy数から現在局面を分類する。
    • 有限状態automatonの構成 — 文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 接尾辞を辞書順に並べるSuffix Array、および複数patternの辞書照合だけを行うAho–Corasick。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題