ABC 433 G — Substring Game
分類・前提・執筆情報
掲載状態: 収録済み
Substring Game の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: Suffix Automatonで部分文字列集合を表す
- 主題
- Suffix Automatonで部分文字列集合を表す: endpos同値類を状態にし、suffix linkと必要なcloneを正しく作って全部分文字列の遷移を線形状態数で表せる。
- 追加で学ぶ技能
- 既習技能
- ゲーム状態の勝敗とGrundy数: 後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。
主タグ: 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。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る