同値な状態を正規化する

概要

並びを逆にしただけの列を同じものとみなすなら、両方を別々に保存する必要はない。「そのままの列と逆順の列のうち、辞書順で小さい方」に統一すれば、同じ対象が必ず同じ形になる。このように、問題の答えに関係しない違いを取り除き、比較や探索に使う形をそろえる操作を正規化という。そろえた形を正規形と呼ぶ。

大切なのは、形を小さくすることよりも、何を同じとみなしてよいかを先に決めることである。並び順を捨ててよい問題でも、同じ値の個数まで捨ててよいとは限らない。また、現在の答えが同じでも、その後の操作で違いが現れるなら、探索の状態としてはまとめられない。

この単元では、具体的な対象から正規形を作り、その対応が正しいことを確かめる方法を学ぶ。さらに、回文のように一部を決めれば全体が決まる対象を、自由な部分だけで表す方法へつなぐ。

考え方

逆向きの列を同じ場所へ保存する

長さ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種類となる。

元の列を ss、逆順にする操作を rev⁡\operatorname{rev} と書く。この例の正規化は、辞書順の小さい方を選ぶ関数

c(s)=min⁡{s,rev⁡(s)}c(s)=\min\{s,\operatorname{rev}(s)\}

である。各入力について逆順を作り、二つを比較し、小さい方を集合へ追加する。最後に集合の要素数を取り出せばよい。回文のように逆順が自分自身と一致するときも、同じ手順で一つだけ保存される。

「同じ正規形」と「同じ種類」を両方向から確かめる

ここで、対象 s,ts,t を同じ種類とみなすことを s∼ts\sim t と書く。先ほどの例では「同じ列であるか、互いに逆順である」ことを表す。この関係は、自分自身と同じ、左右を入れ替えても同じ、同じもの同士をつないでも同じ、という性質を持つ。このような関係を同値関係といい、一種類にまとめられる対象の集まりを同値類という。

正規形で正確に分類するには、次の両方が必要になる。

  • s∼ts\sim t なら c(s)=c(t)c(s)=c(t)。同じ種類を分裂させない。
  • c(s)=c(t)c(s)=c(t) なら s∼ts\sim t。異なる種類を混ぜない。

逆順の例では、同じ種類の二つは候補集合 {s,rev⁡(s)}\{s,\operatorname{rev}(s)\} が等しいので、選ばれる最小の列も等しい。逆に正規形が等しければ、どちらもその列自身か、その逆順である。したがって同じ種類である。この二方向の確認によって、種類と集合に保存された正規形が一対一に対応すると分かる。

操作しても変わらない量を不変量というが、不変量が一つ見つかるだけでは十分とは限らない。列の総和は逆順にしても変わらないものの、(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) になる。次に得られる正規形が違うので、先頭の向きを忘れることはできない。

状態をまとめる前に、同じ正規形を持つ二状態について、次を確認する。

  1. 一方の合法な操作に対して、他方にも同じ正規形へ進む合法な操作がある。逆方向も成り立つ。
  2. 最小費用を求めるなら、対応する操作の費用も等しい。
  3. 終了条件や答えの取り出し方が、正規形から決まる。
  4. 数え上げなら、各遷移先の正規形へ進む選択肢の個数も一致する。

この対応を一手ずつ繰り返せば、元の探索の続きを正規形上でも再現できる。手順は、初期状態を正規化して登録し、取り出した状態から遷移先を作るたびに正規化し、同じキーへまとめる、となる。到達できるかだけなら訪問済みの印、最小費用ならその状態までの最良値、数え上げならそこへ至る個数を保持する。

数え上げでは、同じ正規形へ進む別々の選択を勝手に一回へ減らしてはいけない。例えば区別される二つの選択が同じ遷移先になるなら、その遷移には二通り分を加える。状態を代表化することと、遷移の重複を消すことは別の判断である。

回文は、自由に決める部分だけで一意に表せる

もう一つ、対称性によって表現を小さくする方法がある。ABC242 Eでは、長さが指定された回文のうち、与えられた文字列以下のものを辞書順で数える。ここでは「文字列とその逆順を一組にする」のではなく、各回文そのものを、先頭の半分だけで一意に表す。

長さを NN、自由に選ぶ文字数を h=⌈N/2⌉h=\lceil N/2\rceil とする。偶数長なら前半を反転して後半へ置き、奇数長なら中央の文字を重ねずに反転する。例えば長さ4の前半 BC からは BCCB、長さ5の前半 BCD からは BCDCB ができる。

どの前半からも回文が一つ作れ、どの回文からも元の前半を取り出せる。そのため、前半の列挙には回文の漏れも重複もない。

上限の文字列を SS、その先頭 hh 文字を TT とする。TT より小さい前半を選べば、回文を完成させても、先頭 hh 文字以内で SS より小さいことが確定する。大きい前半なら必ず上限を超える。判断が残るのは、前半が TT と等しい回文一つだけである。

英大文字 A を0、B を1、…、Z を25に対応させると、TT より小さい長さ hh の文字列の個数は、その数字列を26進数とみなした値になる。左から値を読み、初期値0に対して「今の値を26倍して、次の文字の値を足す」を繰り返せば求められる。最後に TT から完成させた回文を SS と比較し、上限以下なら1を加える。

例えば S=BCABS=\texttt{BCAB} なら、前半 BC の値は 1⋅26+2=281\cdot26+2=28。完成する 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に分かれる。ある一入力で結果が等しいだけでは、作用を同じとはみなせない。

操作列 PP が初期値 TT に返す結果を FP(T)F_P(T) とする。すべての許される TT に対して FP(T)=FQ(T)F_P(T)=F_Q(T) なら、PP と QQ の前後に同じ操作列をつないでも結果は変わらない。前にある操作列が作った値をどちらへ渡しても結果が等しく、その等しい結果へ後ろの操作を適用するからである。これが、列の一部分を同じ作用の表現へ置き換えてよい理由になる。

ABC427 Gと公式解説では、列の作用を保ったまま、問い合わせを二分探索で処理できる形へ変える。ここでは作用を保存することと、その表現を速く作ることを分けて考えたい。隣接二要素を定数時間で直せても、挿入のたびに列全体をさかのぼれば、二列の結合は二乗時間になり得る。未処理の値への補正をまとめて持ち、どちらかの列の位置を一つ進める処理にできて初めて、二列の長さの和に比例する結合となる。その後に、同じ長さのブロックをまとめる償却解析へ進める。

また、操作後に失った区別を取り戻せるとは限らない。ABC399 Eの公式解説で扱う文字の一括置換では、一度同じ文字になった二群を後から分けることはできない。異なる目的地へ送りたい群を合流させないこと、循環で値を退避するなら実際に空きを作れることを確かめる。作用や構造を短い表現へ移すときも、元の問題で合法な操作列へ戻せることが必要である。

成立条件と計算量

正規化の候補が見えたら、まず「同じ対象を必ず同じキーへ写すか」「異なる対象を同じキーへ写していないか」を確かめる。操作を続ける問題なら、操作・費用・終了条件の対応も必要になる。単に一方向に到達できることは、一般には対称な関係ではないので、そのまま同値関係として扱えない。

代表の生成にも費用がかかる。長さ LL の列を MM 本分類する場合を考える。

  • 逆順との小さい方を選ぶ処理は、1本につき O(L)O(L) 時間、全体で O(ML)O(ML) 時間である。
  • 任意の並べ替えを同じとみなし、ソートで正規化するなら、生成だけで全体 O(MLlog⁡(L+1))O(ML\log(L+1)) 時間になる。
  • 生成したキーを平衡二分探索木の集合へ登録するなら、列の比較には最悪 O(L)O(L) 時間かかる。登録全体の上界は O(MLlog⁡(M+1))O(ML\log(M+1)) 時間となり、キー比較を整数一つの比較と同じ定数時間にはできない。

異なる正規形が RR 個残るとき、集合の保存量は O(RL)O(RL)。入力を1本ずつ読むなら、これと作業用の O(L)O(L) 領域でよい。全入力を保存する実装なら、別に O(ML)O(ML) の領域を数える。状態数が減っても、代表の生成や保存を含めて制約に収まるかを評価する。

回文を前半だけで表す例では、候補数は英大文字26種類に対して 26h26^h になるが、それらを実際に列挙する必要はない。26進数の値の計算と境界の回文の構築・比較は、合計 O(N)O(N) 時間で行える。文字列全体を保存して回文を構築するなら空間は O(N)O(N)。ABC242 Eでは大きな個数を指定された法で割った余りとして計算する。

座標圧縮も表現を小さくする変換だが、選んだ値の集合の中では、異なる値を異なる順位として残し、大小関係を保つ。正規化で同値な対象をまとめたいのか、値の順序を配列の添字で表したいのかを区別しよう。どちらも、変換後に必要な判定を再現できることが出発点となる。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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では扱わないもの

  • 交換論による貪欲順の証明。

根拠