有限関数・作用の合成
概要
小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。
考え方
長い操作列でも、次の操作から見て必要なのが「今どの状態にいるか」だけなら、操作列全体を一つの関数にまとめられる。状態の集合が小さければ、すべての入力について行き先を書いた表を持てばよい。これにより、操作を順に再実行する代わりに、表を一度参照して結果を得られる。
二入力の表で時間順を追う
状態集合を とする。この集合から同じ集合への関数は、出力表の組 で表せる。可能な表は次の四つだけである。
| 関数 | 入力0 | 入力1 |
|---|---|---|
| 恒等写像 | 0 | 1 |
| 反転 | 1 | 0 |
| 定数写像 | 0 | 0 |
| 定数写像 | 1 | 1 |
例えば、先に 、次に を適用するとどうなるか。二つの入力について、中間状態も書いて確かめる。
| 入力 | ||
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 1 |
合成後の表は 、すなわち である。順序を逆にして、先に 、次に を適用すると、経路は と になる。今度の表は なので、順序を入れ替えてはいけない。
列を左から読む時間順に合わせ、前半の表 と後半の表 の結合を次のように定義する。
まず F[x] で中間状態を求め、その値を後半の表 の添字に使う。数学の合成記号では であり、combine の引数は実行する順に並んでいる。上の例なら combine(C₀,R)=C₁、逆順なら combine(R,C₀)=C₀ となる。
結合則と恒等写像で区間をまとめる
前から三つの表 を適用すると、括り方によらず次の状態へ着く。
これが結合則である。順序を変えずに括り方を変えられるので、操作列を区間ごとにまとめて Segment Tree に載せられる。左の子の表を 、右の子の表を とすれば、親は combine(F,G) で作る。
空列の表は id[x]=x とする。二入力では表が なので、combine(F,id)[x]=id[F[x]]=F[x]、combine(id,F)[x]=F[id[x]]=F[x] となり、左右どちらから結合しても表が変わらない。これが空区間を返すときに使う単位元である。
操作を とすると、先頭から 個の操作をまとめた prefix 表は 、 で作る。区間の表も同じ combine で、元の列の左から右へ結合する。途中の区間でも順序を保つ必要があり、単に取得した節点の順に結合してよいわけではない。求めた表を とすれば、入力状態 に対する結果は T[s] で取り出せる。
多対一の表は prefix から取り除けない
和の累積配列では二つの prefix の差から区間和を求められるが、有限関数では同様に prefix を逆にたどれるとは限らない。 は入力0と1をどちらも0へ送るため、出力0から元の入力を判定できない。失われた情報を逆写像で戻すことはできない。
さらに、prefix が の後に続く操作を考える。後続が恒等写像でも でも、全体の表は同じ になる。しかし後続区間の表はそれぞれ と で異なる。二つの prefix 表だけを知っても、後続が入力1をどこへ送るかは復元できない。任意区間の関数が必要なら、元の操作の区間表を Segment Tree などで保持する。
結合則は括り方を変えられる性質、可換性は順序を交換できる性質、可逆性は元の状態に戻せる性質である。関数合成には結合則があるが、上の例のように可換性や可逆性は一般にはない。この三つを分けて判断しよう。
成立条件と計算量
状態集合の大きさを 、操作の個数を とし、表の一要素の参照を定数時間で行えるとする。一つの表の大きさは 、一合成は全入力の行き先を作るので 時間である。
prefix 表の逐次構築は合計 時間。最新の表だけ残すなら 空間、すべての prefix 表を保存するなら 空間を使う。Segment Tree は 個の節点に表を置くので、構築 時間、空間 、一点の操作変更・区間表の取得はそれぞれ 時間となる。完成した表に一つの入力状態を通すだけなら 時間である。
この方法は、各操作が同じ小さな状態集合上の関数として閉じるときに使う。 が大きければ表そのものが重いので、アフィン変換の係数など、より短い表現を探す必要がある。
ABC261 E の AND・OR・XOR は bit ごとに独立で、一つの bit に注目すると上の四つの表になる。この問題では、毎段階で先頭からの操作列を前回の状態へ再適用する。prefix 表をどう更新するかと、完成した表をどの状態へ適用するかは分けて、問題文から確認しよう。
問題一覧
- ABC261 E「Many Operations」 公式問題
技能・出典
主題: 有限関数・作用の合成(小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 有限関数・作用の合成
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。小さな遷移表を関数として合成し、適用順の逆転を避ける。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 結合的な区間要約・区間分解・合成。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-finite-function-composition
有限関数・作用の合成
習得する技能
- 小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- 有限関数・作用の合成の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。