最小十分状態からDPを設計する

概要

DPで難しいのは、式を立てる前の「何を覚えておけば、過去を使い回せるか」という判断である。履歴をすべて持てば正しくても、状態が多すぎて計算できない。一方、情報を捨てすぎると、将来の選択が違う候補を同じものとして扱ってしまう。

この単元では、未来の振る舞いを基準に履歴をまとめる。足りない状態を反例で見つけ、残した情報から遷移が決まることを確かめ、個数や最小費用を集約するところまでを一つの設計として扱う。「最小十分」は、式を短くすることよりも、正しく区別すべきものだけを区別するための考え方である。

考え方

今いる場所が同じなら、同じ状態だろうか

グラフ上をちょうど LL 回移動し、指定頂点 ss を訪れた回数が偶数になる歩き方を数えるとする。同じ回数だけ歩いて同じ頂点 vv にいても、これまで ss を奇数回訪れた履歴と偶数回訪れた履歴では、同じ続きを付けたときの最終判定が逆になる。位置と移動回数だけにまとめてはならない。

必要なのは訪問回数そのものだろうか。最終条件が偶奇だけなら、0回と2回、1回と3回は同じ扱いにできる。次に ss へ入るたびに偶奇が反転し、それ以外なら維持されるためである。初期頂点を訪問に含めるかも問題の定義で決め、初期値に反映する。

この例で残す状態は「移動済み回数、現在頂点、訪問回数の偶奇」になる。少なすぎる案から出発して反例で必要な情報を足し、その後、回数全体ではなく偶奇だけで十分だと削っている。

同じ続きを与えて区別する

一般に、二つの履歴を同じ状態へまとめたいなら、そこへ同じ操作列を続けたときに何が起こるかを比べる。合法性、次状態、得点や費用の増分、最後の受理条件が変わるなら、二つは区別する必要がある。

ABC215 Eでは、同じ種類を一つのかたまりとして選ぶ。使用集合だけを残す案に対して、AB と BA へ A を付けると、前者だけが不適切になる。末尾だけの案も、AB と CB へ A を付ければ違いが出る。こうして使用集合と末尾の両方が必要だと分かる。

次は十分性を確かめる。二つの情報が同じなら、次文字が現在のかたまりを延長するか、新しい種類を始めるか、禁止された再登場かを同じように判定できる。更新後の集合と末尾も同じになる。この一文字の対応を繰り返せば、どの長さの続きに対しても同じ振る舞いになる。

反例は「この情報を捨てると困る」を教え、遷移規則は「ここまで残せば十分」を教える。小例を多数試して失敗しなかっただけでは、十分性の証明の代わりにならない。

状態のラベルと、そこへ蓄える値を分ける

状態が未来を決める情報なら、その状態へ来る値は、過去の候補をどう集約するかを表す。

求めるもの同じ状態へ来た候補の集約
存在するか一つでも可能なら真
選び方の個数個数を加える
最小費用最小値を残す
最大得点最大値を残す

例えば、同じ状態への費用が7と11なら、今後の選択と追加費用が等しい限り、11の候補が後から逆転することはない。最小化では7だけ残せる。数え上げなら、二つの履歴が別の選び方に当たる限り、二通りとして足さなければならない。

これまでの費用が将来に影響する問題では、話が変わる。残予算で行動が制限されるなら残予算も状態の候補になるし、費用と別の能力に優劣の交換関係があれば、単純に最小費用一個へはまとめられない。最良値だけ残すには、捨てる候補が以後のどの続きでも有利にならない根拠が要る。

覚える情報を減らすために、処理順も設計する

履歴の必要性は、何をこれから処理するかによって変わる。ABC264 Fでは、全行・全列の反転を先に決めると、多数のビットを覚えたくなる。ところが右・下への経路を伸ばす順で決めると、新しく入る行か列の一ビットだけを追加すればよい。

既に離れた行・列には戻らないため、それらのビットは未来へ影響しない。現在の行と列の二ビットが分かれば、隣接マスを同色にする次ビットと追加費用が決まる。ここで、過去の反転操作は値に含む支払い済み費用へ集約し、今後必要な二ビットだけをラベルへ残す。

このように、情報を忘れられるのは「もう使わない」という理由があるときである。左や上へ戻ることを許せば、忘れた行・列を再訪する可能性が生まれ、同じ状態設計は使えなくなる。

遷移式を作った後で、数える単位と更新順を点検する

状態の定義ができたら、何も処理していない時点を初期化し、一操作後の遷移をすべて列挙する。最後に、どの状態から答えを取り出すかを定める。空の選択を入れるか、到達不能をどう表すかも、この意味に合わせる。

数え上げでは、各候補が遷移列へ一意に対応するかが重要になる。ABC215 Eで同じ文字を選ぶ場合と飛ばす場合は同じ状態へ入るが、位置集合が違うため両方を加える。一方、出来上がる文字列の種類数を求める別問題なら、同じ文字列を複数回数えない工夫が必要になる。

更新順も遷移の意味に合わせる。位置 ii の値だけを読んで位置 i+1i+1 を作るなら、二配列を使うと「今回作った値を、同じ操作でもう一度使う」ことを防げる。集合や費用が増えるからといって、その座標だけの降順更新で十分とは限らない。座標が変わらない遷移も含め、どの値を読むべきかを確認する。

右・下だけの経路のように状態間の依存が一方向なら、その順序で走査すればよい。依存に閉路があるなら、通常の一回のDP走査では解けない。状態を作ることと、その状態グラフをどの手法で解くかは別の判断である。

成立条件と計算量

同じ状態にまとめるには、以後の合法な選択と、その選択による変化を残した情報から決められることが必要である。最適化で一つの値だけを残すには、状態が同じ候補の優劣が同じ続きを付けても逆転しないことも確認する。情報を落とす前後で、最終判定に使う条件まで一致させる。

全状態数を SS、一状態から試す選択数を最大 TT とする。各状態を一度処理し、一遷移が定数時間なら、基本の評価は O(ST)O(ST) 時間・O(S)O(S) 空間である。集合の部分集合列挙、配列のコピー、データ構造の操作などがあれば、それらも一遷移または全体の費用へ含める。

位置ごとに S0S_0 状態を持ち、直前の位置だけに依存するなら、長さ NN に対して O(NS0T)O(NS_0T) 時間、DP領域は二層化して O(S0)O(S_0) にできる。ただし入力保存や解の復元に使う領域は別に加える。全履歴を復元したい場合、最良値だけを保存した計算と同じ空間に収まるとは限らない。

状態数を見積もるのは、残す情報の候補を決めた後である。種類数の小さい集合、偶奇、短い末尾、現在の境界などは有力な圧縮先だが、その型へ無理に当てはめない。復習では「何を捨てると区別が必要になるか」「残したものから何が決まるか」を対にして説明できるか確認する。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。未来の選択に必要な情報だけを残し、履歴を同じ状態へまとめる。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-state-design

習得する技能

  • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: automaton上のDP・行列遷移、上限制約付き桁DP、繰り上がり・借り・混合基数を状態にするDP、ゲーム状態の勝敗とGrundy数、minimax・得点差・局面値を評価するゲームDP、グリッド・多次元表の局所DPを設計する、区間合成・領域分割DP、区間拡張DP、prefix分割DP、列・subsequence DP、確率過程・期待値DP、資源・容量DP、部分集合・bitmask状態DP、DP遷移を因数分解・集約して加速する、frontier/profile DP・境界状態圧縮、固定線形遷移を巨大回数進める、根付き木DP・部分木集約。

初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。

このUnitでは扱わないもの

  • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

根拠