接頭辞から更新する有限状態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との比較として扱う。

成立条件と計算量

長さを LL、一つの長さで持つ状態数を SS、選べる数字・文字の種類数を σ\sigma とする。一文字の遷移と個数の加算が定数時間なら、各長さ・状態で文字を試す時間は O(LSσ)O(LS\sigma)。現在と次の長さの配列を分けて更新すれば、DPの作業領域は O(S)O(S) で済む。遷移表を保存する場合は別に O(Sσ)O(S\sigma) の領域と、その構築時間が必要になる。剰余や既出集合などを加えるときは、それらとの組合せも状態数へ含める。

状態へまとめる前に、同じ状態からの合法な文字・遷移先・終端条件が一致することを確かめる。二進列の例では先頭の0も一文字だが、整数の桁DPでは桁数合わせの0を実際の数字として扱うかを決める必要がある。空列や整数0を答えに含めるかも、子単元で初期状態と終端条件へ反映する。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(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。

根拠