automaton上のDP・行列遷移
位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。
この典型を扱う単元: automaton上のDP・行列遷移
検索別名: DFA DP、automaton DP、オートマトンDP
未知問からこの典型を見つける手掛かり
- 扱う対象
- automaton state
- 文字位置
- 遷移表
- 使う手掛かり
- graph walkと有限状態
- patternを避ける
- 長さLの文字列数
- 保つ不変量
- prefix後の状態
- 受理集合
- 求めるもの
- 文字列数え上げ
- 最適walk
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- 上限制約付き桁DP: 数値上限のtight状態を扱うDPと、受理条件を表す有限automatonとの直積DPを区別する。
- 有限状態automatonの構成: 位置・長さと直積する有限状態および完全遷移表をDPの状態基盤にする。
学習成果と学習単位
位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
automaton上のDP・行列遷移で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC228 G「Digits on Grid」 公式問題主題: 非決定性automatonのsubset construction / 主タグ
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC305 G「Banned Substrings」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC391 G「Many LCS」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC419 F「All Included」 公式問題主題: Aho–Corasick / 主タグ
- ABC458 F「Critical Misread」 公式問題主題: Aho–Corasick / 主タグ