同値な状態を正規化する
概要
並びを逆にしただけの列を同じものとみなすなら、両方を別々に保存する必要はない。「そのままの列と逆順の列のうち、辞書順で小さい方」に統一すれば、同じ対象が必ず同じ形になる。このように、問題の答えに関係しない違いを取り除き、比較や探索に使う形をそろえる操作を正規化という。そろえた形を正規形と呼ぶ。
大切なのは、形を小さくすることよりも、何を同じとみなしてよいかを先に決めることである。並び順を捨ててよい問題でも、同じ値の個数まで捨ててよいとは限らない。また、現在の答えが同じでも、その後の操作で違いが現れるなら、探索の状態としてはまとめられない。
この単元では、具体的な対象から正規形を作り、その対応が正しいことを確かめる方法を学ぶ。さらに、回文のように一部を決めれば全体が決まる対象を、自由な部分だけで表す方法へつなぐ。
考え方
逆向きの列を同じ場所へ保存する
長さ3の整数列を何本も受け取り、「逆順にすると一致する列は同じ種類」として種類数を数えることを考える。例えば、次の4本が入力されたとする。
| 入力 | 逆順 | 正規形 |
|---|---|---|
| (5,2,8) | (8,2,5) | (5,2,8) |
| (8,2,5) | (5,2,8) | (5,2,8) |
| (4,1,4) | (4,1,4) | (4,1,4) |
| (5,8,2) | (2,8,5) | (2,8,5) |
辞書順は、先頭から比較して最初に異なる位置の値が小さい方を先とする順序である。1本目と2本目は正規形が一致するので同じ種類、3本目と4本目はそれぞれ別の種類になり、答えは3種類となる。
元の列を 、逆順にする操作を と書く。この例の正規化は、辞書順の小さい方を選ぶ関数
である。各入力について逆順を作り、二つを比較し、小さい方を集合へ追加する。最後に集合の要素数を取り出せばよい。回文のように逆順が自分自身と一致するときも、同じ手順で一つだけ保存される。
「同じ正規形」と「同じ種類」を両方向から確かめる
ここで、対象 を同じ種類とみなすことを と書く。先ほどの例では「同じ列であるか、互いに逆順である」ことを表す。この関係は、自分自身と同じ、左右を入れ替えても同じ、同じもの同士をつないでも同じ、という性質を持つ。このような関係を同値関係といい、一種類にまとめられる対象の集まりを同値類という。
正規形で正確に分類するには、次の両方が必要になる。
- なら 。同じ種類を分裂させない。
- なら 。異なる種類を混ぜない。
逆順の例では、同じ種類の二つは候補集合 が等しいので、選ばれる最小の列も等しい。逆に正規形が等しければ、どちらもその列自身か、その逆順である。したがって同じ種類である。この二方向の確認によって、種類と集合に保存された正規形が一対一に対応すると分かる。
操作しても変わらない量を不変量というが、不変量が一つ見つかるだけでは十分とは限らない。列の総和は逆順にしても変わらないものの、(1, 2, 3) と (1, 1, 4) は総和が等しくても同じ種類ではない。総和だけをキーにすると、二つ目の条件を満たさない。
同様に、ソートした列を正規形にできるのは、任意の並べ替えを同じとみなす場合である。逆順だけを同じとする先ほどの4本をソートすると、1・2・4本目を同じ形にしてしまう。便利な表現を先に選ぶのでなく、許される同一視から表現を導く。
代表を一つ残すことと、元の個数を数えること
正規形の個数が表すのは同値類の数であり、元の対象の数とは異なる。
例えば A, B からなる長さ3の文字列は8個ある。逆順を同じとみなすと、AAB と BAA、ABB と BBA がそれぞれ一組になる。一方、AAA, ABA, BAB, BBB は逆順にしても変化しない。したがって種類数は、二要素の組が2個と、一要素の組が4個で、合計6種類である。8を一律に2で割ると間違う。
元の文字列をすべて数えるなら、正規形ごとに「その形にまとめた元の対象の個数」を持ち、足し合わせる必要がある。対称性を使って種類数を求める理論は、後の群作用・軌道数え上げで扱う。ここでは、同じとみなす基準と、区別して数える基準を混同しないことを押さえたい。
探索の状態をまとめるなら、その先の操作も対応させる
入力を分類するだけなら、正規形が等しいかを調べればよい。しかし、探索やDPで正規形だけを状態として持つなら、元の状態が違っても、今後できる操作とその結果を同じ正規形上で再現できなければならない。
例えば、逆順の列を同じ状態へまとめた後、「先頭の値に1を足す」という操作だけを許すとする。(1, 2, 3) からは (2, 2, 3) へ進む。一方、同じ正規形を持つ (3, 2, 1) からは (4, 2, 1) へ進み、その正規形は (1, 2, 4) になる。次に得られる正規形が違うので、先頭の向きを忘れることはできない。
状態をまとめる前に、同じ正規形を持つ二状態について、次を確認する。
- 一方の合法な操作に対して、他方にも同じ正規形へ進む合法な操作がある。逆方向も成り立つ。
- 最小費用を求めるなら、対応する操作の費用も等しい。
- 終了条件や答えの取り出し方が、正規形から決まる。
- 数え上げなら、各遷移先の正規形へ進む選択肢の個数も一致する。
この対応を一手ずつ繰り返せば、元の探索の続きを正規形上でも再現できる。手順は、初期状態を正規化して登録し、取り出した状態から遷移先を作るたびに正規化し、同じキーへまとめる、となる。到達できるかだけなら訪問済みの印、最小費用ならその状態までの最良値、数え上げならそこへ至る個数を保持する。
数え上げでは、同じ正規形へ進む別々の選択を勝手に一回へ減らしてはいけない。例えば区別される二つの選択が同じ遷移先になるなら、その遷移には二通り分を加える。状態を代表化することと、遷移の重複を消すことは別の判断である。
回文は、自由に決める部分だけで一意に表せる
もう一つ、対称性によって表現を小さくする方法がある。ABC242 Eでは、長さが指定された回文のうち、与えられた文字列以下のものを辞書順で数える。ここでは「文字列とその逆順を一組にする」のではなく、各回文そのものを、先頭の半分だけで一意に表す。
長さを 、自由に選ぶ文字数を とする。偶数長なら前半を反転して後半へ置き、奇数長なら中央の文字を重ねずに反転する。例えば長さ4の前半 BC からは BCCB、長さ5の前半 BCD からは BCDCB ができる。
どの前半からも回文が一つ作れ、どの回文からも元の前半を取り出せる。そのため、前半の列挙には回文の漏れも重複もない。
上限の文字列を 、その先頭 文字を とする。 より小さい前半を選べば、回文を完成させても、先頭 文字以内で より小さいことが確定する。大きい前半なら必ず上限を超える。判断が残るのは、前半が と等しい回文一つだけである。
英大文字 A を0、B を1、…、Z を25に対応させると、 より小さい長さ の文字列の個数は、その数字列を26進数とみなした値になる。左から値を読み、初期値0に対して「今の値を26倍して、次の文字の値を足す」を繰り返せば求められる。最後に から完成させた回文を と比較し、上限以下なら1を加える。
例えば なら、前半 BC の値は 。完成する BCCB は上限を超えるので28個である。上限が BCDA なら同じ28個に BCCB を加え、29個になる。前半が等しいときだけ、後半まで比較する必要がある。この対応と境界判定は公式解説でも確認できる。
主配置問題で、忘れる情報と残す情報を見分ける
ABC250 Eの比較対象は、二つの接頭辞に含まれる値の集合である。出現順と重複回数は比較に不要なので、(7, 4, 7) と (4, 7) は同じ集合になる。ただし、集合の要素数だけでは値の違いを区別できない。まず何を同じとみなすかを定め、そのうえで全クエリを高速に判定する仕組みを組み立てる。公式問題文と公式解説に対応する。
ABC219 Fでは、同じ移動列を繰り返すと、一回分の訪問点集合が一定の変位だけずれて現れる。そこで、同じ変位の整数倍で移り合う点を一組にし、組を表すキーと、その組の中での位置に分ける。組が同じでも実際の訪問点は異なるため、位置の情報まで消してはいけない。訪問点が重なる可能性を正規化で整理し、組の中の重なりは別に数える、という役割分担である。具体的なキーの構成と、変位が0の場合の扱いは公式解説と問題解説へ進む。
同じ値列には、最も早く取れる出現位置を割り当てる
対称操作が明示されていなくても、同じ答えを複数の方法で表しているところに正規化を使える。例えば、列 (2, 1, 2, 1) から部分列 (2, 1) を取り出す位置は、1始まりで (1, 2), (1, 4), (3, 4) の三通りある。位置の選び方を数えるなら別々だが、値列の種類を数えるなら一つにまとめたい。
そこで、欲しい値を先頭から順に、直前に選んだ位置より右で最初に現れる場所から取る。例では (1, 2) が一意な代表になる。この方法で途中までしか取れなくなることはない。実際、同じ値列の任意の取り出し方と比べると、代表の最初の位置はそれ以下である。ある段階で代表の位置が他の取り出し方以下なら、他の取り出し方の次の位置は代表からも選べる候補なので、代表の次の位置もそれ以下になる。これを繰り返せば、取り出せる値列を失わず、最後まで一意に代表を決められる。
ABC446 Gと公式解説では、この最も早い取り出し方を土台に、同じ値の連続部分の末尾を使ってさらに表現を縮める。短くした状態から元の値列を一意に復元できる条件と、空の接頭辞から最初の一塊を作れる境界を確認する必要がある。
連続部分列でも、ABC452 Gの公式解説は、同じ値の連続部分を短い記号列へ変換する例となる。ただし、変換先の出現位置が異なっても値列は一致することがある。表現を短くした後にも、何を一種類と数えるかに従って重複を除く必要がある。
列そのものより、外部への作用を保ちたい場合
操作の列を何度も適用する問題では、見た目が一致する列よりも、「どの初期値から始めても同じ結果になる列」を同じものとして扱いたいことがある。例えば「2を足す」と「2倍する」は、初期値2ではどちらも4になるが、初期値3では5と6に分かれる。ある一入力で結果が等しいだけでは、作用を同じとはみなせない。
操作列 が初期値 に返す結果を とする。すべての許される に対して なら、 と の前後に同じ操作列をつないでも結果は変わらない。前にある操作列が作った値をどちらへ渡しても結果が等しく、その等しい結果へ後ろの操作を適用するからである。これが、列の一部分を同じ作用の表現へ置き換えてよい理由になる。
ABC427 Gと公式解説では、列の作用を保ったまま、問い合わせを二分探索で処理できる形へ変える。ここでは作用を保存することと、その表現を速く作ることを分けて考えたい。隣接二要素を定数時間で直せても、挿入のたびに列全体をさかのぼれば、二列の結合は二乗時間になり得る。未処理の値への補正をまとめて持ち、どちらかの列の位置を一つ進める処理にできて初めて、二列の長さの和に比例する結合となる。その後に、同じ長さのブロックをまとめる償却解析へ進める。
また、操作後に失った区別を取り戻せるとは限らない。ABC399 Eの公式解説で扱う文字の一括置換では、一度同じ文字になった二群を後から分けることはできない。異なる目的地へ送りたい群を合流させないこと、循環で値を退避するなら実際に空きを作れることを確かめる。作用や構造を短い表現へ移すときも、元の問題で合法な操作列へ戻せることが必要である。
成立条件と計算量
正規化の候補が見えたら、まず「同じ対象を必ず同じキーへ写すか」「異なる対象を同じキーへ写していないか」を確かめる。操作を続ける問題なら、操作・費用・終了条件の対応も必要になる。単に一方向に到達できることは、一般には対称な関係ではないので、そのまま同値関係として扱えない。
代表の生成にも費用がかかる。長さ の列を 本分類する場合を考える。
- 逆順との小さい方を選ぶ処理は、1本につき 時間、全体で 時間である。
- 任意の並べ替えを同じとみなし、ソートで正規化するなら、生成だけで全体 時間になる。
- 生成したキーを平衡二分探索木の集合へ登録するなら、列の比較には最悪 時間かかる。登録全体の上界は 時間となり、キー比較を整数一つの比較と同じ定数時間にはできない。
異なる正規形が 個残るとき、集合の保存量は 。入力を1本ずつ読むなら、これと作業用の 領域でよい。全入力を保存する実装なら、別に の領域を数える。状態数が減っても、代表の生成や保存を含めて制約に収まるかを評価する。
回文を前半だけで表す例では、候補数は英大文字26種類に対して になるが、それらを実際に列挙する必要はない。26進数の値の計算と境界の回文の構築・比較は、合計 時間で行える。文字列全体を保存して回文を構築するなら空間は 。ABC242 Eでは大きな個数を指定された法で割った余りとして計算する。
座標圧縮も表現を小さくする変換だが、選んだ値の集合の中では、異なる値を異なる順位として残し、大小関係を保つ。正規化で同値な対象をまとめたいのか、値の順序を配列の添字で表したいのかを区別しよう。どちらも、変換後に必要な判定を再現できることが出発点となる。
問題一覧
- ABC462 E「Alternating Costs」 公式問題組合せ: 一次元凸・単峰最適化
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 状態・配置の正規化 / 補助タグ: 一次元凸・単峰最適化
- ABC242 E「(∀x∀)」 公式問題
技能・出典
主題: 同値な状態を正規化する(鏡映対称な文字列を自由な前半で一意に表し、辞書順上限以下の個数を前半prefixの基数値と、等号境界の完成文字列一候補との比較で求められる。)。主タグ: 状態・配置の正規化
- ABC250 E「Prefix Equality」 公式問題
- ABC323 F「Push and Carry」 公式問題
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 状態・配置の正規化 / 補助タグ: 有界全列挙・有限case分解、幾何の基本判定・配置・座標変換
- ABC296 F「Simultaneous Swap」 公式問題
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 状態・配置の正規化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC302 G「Sort from 1 to 4」 公式問題
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 状態・配置の正規化 / 補助タグ: 有界全列挙・有限case分解
- ABC446 G「221 Subsequence」 公式問題組合せ: DP遷移を因数分解・集約して加速する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。 各値列の辞書順最小添字列だけを数える正準化から、直前位置の開区間L_p<j<R_pを導く。dp[p]=Σ dp[j]をrange sumとpoint addへ写し、O(N²)をO(N log N)へ減らす。主タグ: 状態・配置の正規化 / 補助タグ: DP遷移の集約・高速化
- ABC463 F「Senshuraku」 公式問題
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 状態・配置の正規化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC313 G「Redistribution of Piles」 公式問題組合せ: 格子点転置によるfloor_sum
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 格子点転置によるfloor_sum(Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。)。主タグ: 状態・配置の正規化 / 補助タグ: 格子点転置によるfloor_sum
- ABC219 F「Cleaning Robot」 公式問題
- ABC427 G「Takahashi's Expectation 2」 公式問題組合せ: 単調進行による償却解析、単調境界を証明して探索する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: 状態・配置の正規化 / 補助タグ: 単調進行による償却解析、単調境界探索
- ABC382 G「Tile Distance 3」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 H「Red and Blue Lamps」 公式問題
技能・出典
主題: path matchingのheap縮約greedy(重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 要素索引と連結リストで局所linkを更新する(要素IDから前後linkを引き、挿入・削除で変わる局所linkだけを更新して列順を復元できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: path matchingのheap縮約greedy / 補助タグ: 索引付き連結リスト、priority queue・best-first列挙、状態・配置の正規化
- ABC232 H「King's Tour」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 構成解・witness復元 / 補助タグ: 状態・配置の正規化
- ABC278 G「Generalized Subtraction Game」 公式問題主題: ゲーム状態の勝敗とGrundy数
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: game状態・Grundy DP / 補助タグ: 対話protocolとquery設計、状態・配置の正規化
- ABC284 G「Only Once」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC307 E「Distinct Adjacent」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。 - ABC360 E「Random Swaps of Balls」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 確率・期待値DP / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC404 F「Lost and Pound」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。)。既習技能: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。 - ABC411 G「Count Cycles」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC421 E「Yacht」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。)。既習技能: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。 - ABC425 F「Inserting Process」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 状態・配置の正規化
- ABC450 G「Random Subtraction」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 確率・期待値DP / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。対称性で同じ候補をまとめ、代表だけを残してよい理由を示せるようにする。
対象色の読み方は本書の読み方を参照してください。
概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-normalization
習得する技能
- 鏡映対称な文字列を自由な前半で一意に表し、辞書順上限以下の個数を前半prefixの基数値と、等号境界の完成文字列一候補との比較で求められる。
- 対称操作で同値な状態の標準形と不変量を選べる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 群作用・軌道数え上げ。
対称な状態を同一視できると探索やDPの状態数を減らせるため、同値類の標準形と不変量を先に定める。
このUnitでは扱わないもの
- 交換論による貪欲順の証明。