接頭辞から更新する有限状態DP
概要
数字や文字を左から一つずつ決めるとき、既に決めた部分を接頭辞という。接頭辞そのものは指数的に増えるが、続きを選ぶために必要な情報が同じなら、一つの状態へまとめられる。この考え方を入口に、文字列の制約を扱うautomaton上のDPと、数値上限を扱う桁DPへ進む。
考え方
例えば、11を連続する部分文字列として含まない二進列を数えたい。まだ11を含んでいない接頭辞000と010は、どちらも末尾が0である。次に0も1も置け、その先も全く同じ続きを付けられる。末尾が1の001と101も同じ続きを付けられるが、こちらは次に1を置くと違反する。
従って、処理した長さごとに「末尾が1か」だけを残し、同じ状態に至る接頭辞の個数を足せばよい。空列は、次に0も1も置けるので末尾0側と同じ状態に置く。同じ状態なら、どの続きを付けられ、最後に条件を満たすかも同じであることが、履歴を捨ててよい理由である。この二状態の遷移と数え上げは、子単元のautomaton上のDP・行列遷移で追う。
一方、数値上限があると、末尾だけでは次の桁を選べない。上限を二進数の100とし、候補も3桁へ0埋めして比べる。2桁目までの10と00はともに末尾0だが、前者に1を足すと上限を超え、後者なら超えない。そこで「ここまで上限の接頭辞と一致しているか」を追加する。一致中は次の桁を上限の対応桁以下に制限し、既に小さければ残りは自由に選べる。これが上限制約付き桁DPの追加情報であり、文字列の制約もあれば両方を状態に持つ。
加算の繰り上がり(carry)も短い情報を次へ渡すが、自然な処理方向は下位桁からである。本単元の範囲は左から接頭辞を伸ばすDPとし、carryは別単元の繰り上がり・借り・混合基数を状態にするDPとの比較として扱う。
成立条件と計算量
長さを 、一つの長さで持つ状態数を 、選べる数字・文字の種類数を とする。一文字の遷移と個数の加算が定数時間なら、各長さ・状態で文字を試す時間は 。現在と次の長さの配列を分けて更新すれば、DPの作業領域は で済む。遷移表を保存する場合は別に の領域と、その構築時間が必要になる。剰余や既出集合などを加えるときは、それらとの組合せも状態数へ含める。
状態へまとめる前に、同じ状態からの合法な文字・遷移先・終端条件が一致することを確かめる。二進列の例では先頭の0も一文字だが、整数の桁DPでは桁数合わせの0を実際の数字として扱うかを決める必要がある。空列や整数0を答えに含めるかも、子単元で初期状態と終端条件へ反映する。
下位単元
- 上限制約付き桁DP — 水色
- automaton上のDP・行列遷移 — 青色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC228 G「Digits on Grid」 公式問題
技能・出典
主題: 非決定性automatonのsubset construction(同時に存在し得るNFA状態集合を一つのDFA状態とし、文字ごとの集合遷移と受理条件を構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: automaton上のDP・行列遷移、非決定性automatonのsubset construction / 補助タグ: 部分集合・bitmask状態DP
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC305 G「Banned Substrings」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 線形遷移・行列累乗
- ABC391 G「Many LCS」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: DPの最小十分状態 / 補助タグ: automaton上のDP・行列遷移
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: DPの最小十分状態、区間合成・領域分割DP
- ABC419 F「All Included」 公式問題主題: Aho–Corasick
技能・出典
主題: Aho–Corasick(複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: Aho–Corasick、automaton上のDP・行列遷移 / 補助タグ: 部分集合・bitmask状態DP
- ABC458 F「Critical Misread」 公式問題主題: Aho–Corasick
技能・出典
主題: Aho–Corasick(複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。主タグ: Aho–Corasick、automaton上のDP・行列遷移 / 補助タグ: 線形遷移・行列累乗
前提・学習成果・出典
導入対象の目安: 水色(1200–1599)。prefixの有限情報だけを持つDPを、桁の上限や文字列の制約へ使う入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-digit-string
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 整除鎖・加算式のcarryだけを下位桁から渡すDP、および接頭辞状態を使わない一般の表DP。