有限関数・作用の合成

概要

小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。

考え方

長い操作列でも、次の操作から見て必要なのが「今どの状態にいるか」だけなら、操作列全体を一つの関数にまとめられる。状態の集合が小さければ、すべての入力について行き先を書いた表を持てばよい。これにより、操作を順に再実行する代わりに、表を一度参照して結果を得られる。

二入力の表で時間順を追う

状態集合を {0,1}\{0,1\} とする。この集合から同じ集合への関数は、出力表の組 (F[0],F[1])(F[0],F[1]) で表せる。可能な表は次の四つだけである。

関数入力0入力1
恒等写像 id\mathrm{id}01
反転 RR10
定数写像 C0C_000
定数写像 C1C_111

例えば、先に C0C_0、次に RR を適用するとどうなるか。二つの入力について、中間状態も書いて確かめる。

入力 xxC0[x]C_0[x]R[C0[x]]R[C_0[x]]
001
101

合成後の表は (1,1)(1,1)、すなわち C1C_1 である。順序を逆にして、先に RR、次に C0C_0 を適用すると、経路は 0→1→00\to1\to0 と 1→0→01\to0\to0 になる。今度の表は (0,0)(0,0) なので、順序を入れ替えてはいけない。

列を左から読む時間順に合わせ、前半の表 FF と後半の表 GG の結合を次のように定義する。

combine⁡(F,G)[x]=G[F[x]]\operatorname{combine}(F,G)[x]=G[F[x]]

まず F[x] で中間状態を求め、その値を後半の表 GG の添字に使う。数学の合成記号では G∘FG\circ F であり、combine の引数は実行する順に並んでいる。上の例なら combine(C₀,R)=C₁、逆順なら combine(R,C₀)=C₀ となる。

結合則と恒等写像で区間をまとめる

前から三つの表 F,G,HF,G,H を適用すると、括り方によらず次の状態へ着く。

combine⁡(combine⁡(F,G),H)[x]=H[G[F[x]]],combine⁡(F,combine⁡(G,H))[x]=H[G[F[x]]].\begin{aligned} \operatorname{combine}(\operatorname{combine}(F,G),H)[x]&=H[G[F[x]]],\\ \operatorname{combine}(F,\operatorname{combine}(G,H))[x]&=H[G[F[x]]]. \end{aligned}

これが結合則である。順序を変えずに括り方を変えられるので、操作列を区間ごとにまとめて Segment Tree に載せられる。左の子の表を FF、右の子の表を GG とすれば、親は combine(F,G) で作る。

空列の表は id[x]=x とする。二入力では表が (0,1)(0,1) なので、combine(F,id)[x]=id[F[x]]=F[x]、combine(id,F)[x]=F[id[x]]=F[x] となり、左右どちらから結合しても表が変わらない。これが空区間を返すときに使う単位元である。

操作を f1,…,fNf_1,\ldots,f_N とすると、先頭から ii 個の操作をまとめた prefix 表は P0=idP_0=\mathrm{id}、Pi=combine⁡(Pi−1,fi)P_i=\operatorname{combine}(P_{i-1},f_i) で作る。区間の表も同じ combine で、元の列の左から右へ結合する。途中の区間でも順序を保つ必要があり、単に取得した節点の順に結合してよいわけではない。求めた表を TT とすれば、入力状態 ss に対する結果は T[s] で取り出せる。

多対一の表は prefix から取り除けない

和の累積配列では二つの prefix の差から区間和を求められるが、有限関数では同様に prefix を逆にたどれるとは限らない。C0C_0 は入力0と1をどちらも0へ送るため、出力0から元の入力を判定できない。失われた情報を逆写像で戻すことはできない。

さらに、prefix が C0C_0 の後に続く操作を考える。後続が恒等写像でも C0C_0 でも、全体の表は同じ C0C_0 になる。しかし後続区間の表はそれぞれ (0,1)(0,1) と (0,0)(0,0) で異なる。二つの prefix 表だけを知っても、後続が入力1をどこへ送るかは復元できない。任意区間の関数が必要なら、元の操作の区間表を Segment Tree などで保持する。

結合則は括り方を変えられる性質、可換性は順序を交換できる性質、可逆性は元の状態に戻せる性質である。関数合成には結合則があるが、上の例のように可換性や可逆性は一般にはない。この三つを分けて判断しよう。

成立条件と計算量

状態集合の大きさを σ\sigma、操作の個数を NN とし、表の一要素の参照を定数時間で行えるとする。一つの表の大きさは O(σ)O(\sigma)、一合成は全入力の行き先を作るので O(σ)O(\sigma) 時間である。

prefix 表の逐次構築は合計 O(Nσ)O(N\sigma) 時間。最新の表だけ残すなら O(σ)O(\sigma) 空間、すべての prefix 表を保存するなら O(Nσ)O(N\sigma) 空間を使う。Segment Tree は O(N)O(N) 個の節点に表を置くので、構築 O(Nσ)O(N\sigma) 時間、空間 O(Nσ)O(N\sigma)、一点の操作変更・区間表の取得はそれぞれ O(σlog⁡N)O(\sigma\log N) 時間となる。完成した表に一つの入力状態を通すだけなら O(1)O(1) 時間である。

この方法は、各操作が同じ小さな状態集合上の関数として閉じるときに使う。σ\sigma が大きければ表そのものが重いので、アフィン変換の係数など、より短い表現を探す必要がある。

ABC261 E の AND・OR・XOR は bit ごとに独立で、一つの bit に注目すると上の四つの表になる。この問題では、毎段階で先頭からの操作列を前回の状態へ再適用する。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では扱わないもの

  • 有限関数・作用の合成の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠