局所寄与へ分解して集計順を交換する

概要

すべての区間や組について得点を計算し、その総和を求める問題では、同じ要素を何度も調べがちです。そこで、得点を小さな加算の単位へ分解し、一つの単位を固定して、それが答えに何回現れるかを先に数えます。この見方を寄与の数え上げ、あるいは主客転倒と呼びます。

たとえば、配列のすべての区間和を足すなら、各要素の値に「その位置を含む区間の個数」を掛けて足せます。しかし、区間内の値の種類数を足すときは、同じ値の要素を別々に数えると重複します。高速化の前に、何を一回として数えるかを決めることがこの単元の中心です。

以下では、要素を固定する小例から始め、重複を防ぐ代表の決め方、三つ組の中央を固定する方法、指示変数による期待値の分解へ進みます。有限和の順序交換を自分で組み立て、固定した後に残る計算まで評価できることを目指します。

考え方

区間を作る側から、区間に含まれる側へ

配列 A=(2,1,2)A=(2,1,2) の、空でないすべての連続区間の和を、さらに足すことを考えます。区間を左から順に挙げると、

2+3+5+1+3+2=162+3+5+1+3+2=16

です。最初の三項は左端が1、次の二項は左端が2、最後の一項は左端が3の区間に対応します。

長さを NN とすると、区間は N(N+1)/2N(N+1)/2 個あります。各区間内を走査する素朴解は時間 O(N3)O(N^3)、累積和で一つの区間和を定数時間で得ても全体で O(N2)O(N^2) です。求めるものは総和一つなので、区間をすべて作らずに計算する余地があります。

同じ位置の要素が、複数の区間和に現れることに注目します。位置は1始まりとし、位置 ii を固定しましょう。区間の左端を ll、右端を rr とすると、その要素を含む条件は

1≤l≤i≤r≤N1\leq l\leq i\leq r\leq N

です。左端には ii 通り、右端には N−i+1N-i+1 通りの選択があります。どの左端と右端を組み合わせても有効であり、一つの区間の端点は一意なので、位置 ii は i(N−i+1)i(N-i+1) 個の区間に含まれます。

位置値区間数寄与
121×3=31\times3=36
212×2=42\times2=44
323×1=33\times1=36

先ほど区間ごとに足した16を、今度は 6+4+66+4+6 と計算できました。一般にも、答えは

∑i=1NAi i(N−i+1)\sum_{i=1}^{N} A_i\,i(N-i+1)

です。要素を一度ずつ処理すればよいので時間は O(N)O(N)。入力を順に読んで加算すれば追加空間は O(1)O(1)、配列を保存する実装なら全空間は O(N)O(N) です。

順序を変えても、足す項は変えない

この変形が正しい理由を、他の問題でも使える形にします。完成した区間・選択などの集合を C\mathcal C、得点を分解した単位の集合を UU とします。一つの完成形 c∈Cc\in\mathcal C において、単位 u∈Uu\in U が持つ寄与を q(c,u)q(c,u) と定義します。関係しない組には寄与0を与えれば、総和は

∑c∈C∑u∈Uq(c,u)=∑u∈U∑c∈Cq(c,u)\sum_{c\in\mathcal C}\sum_{u\in U}q(c,u) = \sum_{u\in U}\sum_{c\in\mathcal C}q(c,u)

と書けます。どちらも同じ有限個の組 (c,u)(c,u) の寄与を一度ずつ足しているため、足す順を変えられます。寄与に負数があっても、この等式は成立します。

区間和の例では UU は位置の集合で、q([l,r],i)q([l,r],i) は、l≤i≤rl\leq i\leq r なら AiA_i、それ以外は0です。左辺は「区間を選び、中の要素を足す」、右辺は「位置を選び、その要素を含む区間の分だけ足す」に対応します。

以降、条件 PP が成立すれば1、成立しなければ0となる記号を [P][P] と書きます。この0か1の量を指示変数と呼びます。たとえば q([l,r],i)=Ai[l≤i≤r]q([l,r],i)=A_i[l\leq i\leq r] です。

大切なのは、式の順序交換だけでは計算量は減らないことです。すべての組を改めて列挙すれば元と同じです。区間和では、固定した位置に対する内側の和を、端点の選択数の積で定数時間にまとめたことが高速化になっています。

種類数では、区間内の最初の出現へ割り当てる

同じ A=(2,1,2)A=(2,1,2) で、今度はすべての区間に含まれる「異なる値の種類数」を足してみます。六つの区間の種類数は、先ほどと同じ順に 1,2,2,1,2,11,2,2,1,2,1 で、総和は9です。

各位置を含む区間数をそのまま足すと 3+4+3=103+4+3=10 となり、一つ多くなります。区間 [1,3][1,3] に値2が二つあるためです。この区間の種類数には値2を一回だけ加えたいのに、位置1と位置3から二回加えてしまいました。

正しい加算単位は「区間と、その区間に含まれる値の組」です。入力に現れる値の集合を VV とすると、

∑1≤l≤r≤N ∑x∈V[x が Al,…,Ar に現れる]\sum_{1\leq l\leq r\leq N}\ \sum_{x\in V} [x\text{ が }A_l,\ldots,A_r\text{ に現れる}]

を計算したいわけです。出現する回数によらず、各値の指示変数は1以下になります。

値を固定した後も、同じ値の複数の位置をどう扱うかが残ります。そこで、各区間について、その値の区間内で最も左の出現を代表にします。値が現れるなら代表が必ず一つあり、現れなければ代表はありません。

位置 ii より前で AiA_i と同じ値が最後に現れた位置を pip_i とします。前に現れなければ pi=0p_i=0 とします。位置 ii が区間内の最初の出現になる条件は、

pi<l≤i≤r≤Np_i<l\leq i\leq r\leq N

です。l≤pil\leq p_i なら前の出現まで含んでしまい、l>pil>p_i なら ll から i−1i-1 に同じ値はありません。したがって左端は i−pii-p_i 通り、右端は N−i+1N-i+1 通りであり、位置 ii に割り当てる寄与は

(i−pi)(N−i+1)(i-p_i)(N-i+1)

となります。

位置直前の出現左端の候補区間数
1011×3=31\times3=3
201, 22×2=42\times2=4
312, 32×1=22\times1=2

値2の寄与は位置1と位置3に分かれて 3+2=53+2=5、値1の寄与は4です。区間 [1,3][1,3] の値2は位置1だけが担当し、位置3は担当しません。こうして 5+4=95+4=9 を重複なく得られます。

実装では、各値の直前の出現位置を last に保存し、左から走査します。たとえば 1≤Ai≤N1\leq A_i\leq N なら、次の擬似コードで計算できます。

last[1..N] = 0
answer = 0
for i = 1..N:
    x = A[i]
    answer += (i - last[x]) * (N - i + 1)
    last[x] = i
return answer

位置 ii の処理前に、last[x] は位置 i−1i-1 までの最後の出現を表します。加算後に更新するので、この意味が次の位置でも保たれます。先に更新すると自分自身を前の出現にしてしまい、寄与が0になるため、操作順も条件式の一部です。

初期化と走査を合わせて時間 O(N)O(N)、last と入力保存を含めた空間は O(N)O(N) です。値が大きく配列の添字にできない場合は、ソートによる座標圧縮や平衡木の連想配列を使えば時間 O(Nlog⁡N)O(N\log N)、空間 O(N)O(N) で処理できます。

別の数え方として、固定した値を含まない区間を全区間から引く方法もあります。その値の出現位置の間にある、値を含まない連続部分を考えましょう。配列の両端の部分も含め、それぞれの長さを g0,…,gmg_0,\ldots,g_m とします。ここで mm はその値の出現回数です。値を含まない区間は必ず一つの部分に収まり、異なる部分にまたがることはありません。よって、その値を含む区間数は

N(N+1)2−∑t=0mgt(gt+1)2\frac{N(N+1)}2-\sum_{t=0}^{m}\frac{g_t(g_t+1)}2

です。例の値2では、出現位置1と3の間の長さ1だけが寄与し、6−1=56-1=5 となります。これはABC371 Eの公式解説の数え方です。値別に出現位置を並べて処理しても、全部の出現回数の和は NN、部分の総数は N+∣V∣N+|V| なので、全体で線形時間に収まります。

代表へ割り当てる方法と、含まない範囲を引く方法は、同じ「値と区間の組」を別の分け方で数えています。どちらでも、何が一意に決まり、何を一回だけ数えるかを言えることが正当性の核です。

三つ組は、中央を固定して残りを分類する

三つの位置 i<j<ki<j<k を選ぶ問題では、中央 jj を固定すると、残りの位置の条件を i<ji<j と k>jk>j に分けられます。左端 ii だけを固定した場合は、まだ j<kj<k という関係が残るので、中央固定をまず試す理由があります。

ただし、左右の候補数をそのまま掛けてよいかは、位置以外の条件にもよります。残った条件が左右を結び付けるなら、条件を確認せずに全候補数を掛けることはできません。

ABC308 E「MEX」では、文字列から M, E, X をこの順に選び、対応する三つの値の mex を足します。mexとは、それらに含まれない最小の非負整数です。値はいずれも0, 1, 2です。

仕組みを見るため、次の小例を使います。

位置:  1 2 3 4 5
文字:  M M E X X
値:    0 0 1 2 0

中央は位置3に決まります。左に M が2個、右に X が2個あるため、三つ組は4個です。しかし得点は一様ではありません。

  • 右に位置4の値2を選ぶ2組は、値が (0,1,2)(0,1,2) なので mex は3。寄与は 2×1×3=62\times1\times3=6。
  • 右に位置5の値0を選ぶ2組は、値が (0,1,0)(0,1,0) なので mex は2。寄与は 2×1×2=42\times1\times2=4。

合計は10です。添字を一つずつ区別する代わりに、同じ得点になる値の組へまとめ、その組数を掛けると計算できます。

一般に、中央 jj より左にある「値 aa の M」の個数を Lj[a]L_j[a]、右にある「値 bb の X」の個数を Rj[b]R_j[b] とします。Sj=ES_j=\mathrm E である中央一つの寄与は、

∑a=02∑b=02Lj[a]Rj[b]mex⁡(a,Aj,b)\sum_{a=0}^{2}\sum_{b=0}^{2} L_j[a]R_j[b]\operatorname{mex}(a,A_j,b)

です。j,a,bj,a,b を固定すれば得点が決まり、その分類内では左右のどの候補を組み合わせても有効です。また、各三つ組は中央と左右の値を一意に持つので、異なる分類へ重複して入りません。

毎回左右を数え直すと O(N2)O(N^2) 時間かかります。左の個数をすべて0、右の個数を入力全体の X の個数で初期化し、中央を左から右へ動かします。現在位置が X なら先に右から除き、E なら9通りの値の組を加算し、M なら最後に左へ加えます。この順にすれば、寄与を求める時点で左は i<ji<j、右は k>jk>j だけを数えます。

初期集計を含めて時間 O(N)O(N)、左右のカウンタは計6個です。入力の配列と文字列を保存するので、全空間は O(N)O(N)、入力以外の追加空間は O(1)O(1) です。公式解説のように値別の累積和を用意しても、同じ式を評価できます。

ABC318 E「Sandwiches」では、同じ中央固定でも左右の値を等しくし、中央とは異なる値に限ります。左右を値別に数え、同じ値同士の個数の積を足す必要があります。値の種類は最大 NN なので、各中央で全値を調べると二次時間です。固定による式の簡略化に加え、中央を動かしたときにどの集計値だけが変わるかを見る段階へ進みます。

期待値は、各単位が現れる確率を足す

「種類数の期待値」も、種類ごとに指示変数を置けば同じ見方で扱えます。まず、赤2個・青1個・緑1個のキャンディから、2個を一様に選ぶ例を考えましょう。同じ赤でも二つのキャンディは別物です。

選び方は6通りあり、赤同士の1通りは1色、それ以外の5通りは2色なので、種類数の期待値は 11/611/6 です。これを、色ごとに数え直します。

赤が選ばれたら1、選ばれなければ0となる指示変数を IRI_{\mathrm R} とし、青・緑にも IB,IGI_{\mathrm B},I_{\mathrm G} を定めます。どの選択結果でも、種類数 XX は

X=IR+IB+IGX=I_{\mathrm R}+I_{\mathrm B}+I_{\mathrm G}

です。赤を含む選び方は、青と緑だけを選ぶ1通りを除いた5通りです。青を含む選び方は残り3個から相手を選ぶ3通りで、緑も同様です。したがって

E[X]=56+36+36=116\mathbb E[X]=\frac56+\frac36+\frac36=\frac{11}{6}

となります。

ここで、色の登場は独立ではありません。青と緑が両方選ばれる確率は 1/61/6 であり、それぞれの確率の積 1/2×1/2=1/41/2\times1/2=1/4 と異なります。それでも期待値を足せる理由を確認します。

起こり得る結果の有限集合を Ω\Omega、結果 ω\omega の確率を pωp_\omega とします。期待値は「各結果の値にその確率を掛けた総和」です。種類などの集合 UU に対して X(ω)=∑u∈UIu(ω)X(\omega)=\sum_{u\in U}I_u(\omega) と書けるなら、

E[X]=∑ω∈Ωpω∑u∈UIu(ω)=∑u∈U∑ω∈ΩpωIu(ω)=∑u∈UPr⁡(Iu=1)\begin{aligned} \mathbb E[X] &=\sum_{\omega\in\Omega}p_\omega\sum_{u\in U}I_u(\omega)\\ &=\sum_{u\in U}\sum_{\omega\in\Omega}p_\omega I_u(\omega)\\ &=\sum_{u\in U}\Pr(I_u=1) \end{aligned}

です。二行目は有限和の順序交換、三行目は指示変数が1になる結果の確率だけを足す操作です。これが期待値の線形性であり、独立性を仮定する箇所はありません。各単位に結果によらない重み wuw_u が付く場合も、X=∑uwuIuX=\sum_u w_uI_u と分ければ、E[X]=∑uwuPr⁡(Iu=1)\mathbb E[X]=\sum_u w_u\Pr(I_u=1) となります。

ABC215 G「Colorful Candies 2」では、NN 個から KK 個を一様に選びます。ある色が nxn_x 個あるとき、その色を少なくとも一つ選ぶ確率は、「その色を一つも選ばない確率」を引けば求まります。

Pr⁡(Ix=1)=1−(N−nxK)(NK)\Pr(I_x=1)=1-\frac{\binom{N-n_x}{K}}{\binom NK}

ここで (ab)\binom ab は aa 個から bb 個を選ぶ組合せ数で、b>ab>a なら0とします。分子はその色以外から選ぶ場合の数、分母は全選択の場合の数です。各色についてこの確率を足せば、色の組合せ全体を列挙せずに期待値を得られます。

ただし、これで全体の高速化が終わるとは限りません。この問題はすべての K=1,…,NK=1,\ldots,N に答えるため、組合せ数を定数時間で計算できても、毎回全色を走査すれば最悪 O(N2)O(N^2) 時間です。個別解説では、確率が色の個数 nxn_x だけに依存することを使い、同じ個数の色をまとめるところまで進みます。

成立条件と計算量

固定する軸は、残った条件から選ぶ

最初に、完成形一つの得点をどの単位の和にできるかを考えます。そのうえで、各単位を固定したときに残る条件を式にします。要素・値・中央・端点のどれを選ぶかは、その条件を少ない情報で数えられるかによって決まります。

  • 要素を固定する。 区間和の総和のように、含まれるたびに値を加えるなら位置ごとに分ける。左右の端点が自由に選べれば、個数の積へまとめられる。
  • 値を固定する。 種類数のように、何回現れても一回だけ加えるなら値ごとの指示変数にする。複数の出現がある場合は、一意な代表へ割り当てるか、その値を含まない場合を引く。
  • 中央を固定する。 順序付き三つ組で、左右の位置条件を分離したいときに試す。残る値の条件や得点によって候補を分類し、分類内の選択がすべて有効かを確認する。
  • 端点を固定する。 右端を一つ進めたときに、条件を満たす左端の範囲や寄与の変化だけを更新できるなら、区間全体を作り直す必要がなくなる。

たとえばABC247 E「Max Min」では、区間の最大値と最小値を指定します。条件は区間内の値を一つずつ加える形には分かれませんが、右端を固定すると、必要な値の最後の出現と、許されない値の最後の出現から左端の範囲を数えられます。一つの集計軸で数えにくいときは、完成形を別の一意な軸で分け直す候補を持ちましょう。

和へ分けられることと、各項を安く求められることを分ける

順序交換は、有限個の寄与を加算する場合に使えます。整数を法で扱う加算でも同様です。一方、最大値を要素の値の和へ置き換えるなど、元の得点と一致しない分解はできません。最大値を値ごとの指示変数へ分解するなら、その等式自体を別途導く必要があります。

計算量は、固定する対象の個数 × 一対象の寄与を求める費用に、初期化・ソート・前計算を加えて評価します。種類別の式ができても、種類数が多ければ重いままです。今回の三つ組で速かったのは、左右の値が3種類ずつで、移動時の更新も定数回で済んだからです。値別の累積和や頻度表、必要ならFenwick Treeなど、内側の集計を処理する道具は条件に合わせて選びます。

累積和は区間の情報を取り出す道具で、寄与分解は何を足すかを設計する考え方です。両者は組み合わせて使えます。また、時刻順の更新を扱う問題でも、「各時刻の全要素を更新する」処理を「一要素が有効だった期間の寄与」へ交換できる場合があります。ABC347 E「Set Add Query」は、その接続を学ぶ問題です。時刻順の走査自体の設計はevent sweepの単元で扱います。

境界では、何を一回とするかを確かめる

区間の最初の出現へ割り当てる式では、前の出現がないときの0が左端1を許します。隣接した同値要素でも、後ろの要素が最初になる左端はその位置一つだけあり、i−pi=1i-p_i=1 になります。すべて同じ値なら種類数は各区間で1なので、答えは N(N+1)/2N(N+1)/2。すべて異なれば種類数は区間長に等しく、位置を含む区間数を足す式と一致します。

中央固定では現在位置を左右両方から除き、厳密な i<j<ki<j<k を守ります。左または右に候補がなければ積は0です。確率では、一様に選ぶときだけ「場合の数の比」をそのまま使えます。一様でなくても期待値の線形性は成立しますが、各結果の実際の確率を用いる必要があります。

中間値の大きさも確認します。区間ごとの種類数の総和は最大で

∑i=1Ni(N−i+1)=N(N+1)(N+2)6\sum_{i=1}^{N}i(N-i+1)=\frac{N(N+1)(N+2)}6

です。これは各区間の長さの総和でもあります。32 bit整数では不足する入力があり、要素の値や得点を掛ける問題ではさらに大きくなります。代入先だけでなく、積の計算を始める型から必要な幅を確保します。

この単元から問題一覧へ進むときは、一つの完成形の得点を分ける → 加算単位を固定する → 漏れと重複を確認する → 内側の集計をまとめる、という順で自分の式を作ってみてください。まずABC371 Eで代表と余事象を、ABC318 E・ABC308 Eで中央固定と値別集計を確かめると、同じ「総和」の要求でも固定すべき軸が変わる理由を比較できます。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。要素・組・値・区間のどれを固定すれば一意に数えられるかを見抜き、総和の順を交換する。

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

概念上の親: モデル変換とアルゴリズム設計。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-contribution-reordering

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

数える対象を一意に固定し、その対象を含む選択や組の個数へ集計順を交換する。要素・組・区間・値のどれを固定すると重複が消えるかを比較する。

このUnitでは扱わないもの

  • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

根拠

本文の具体例と式は、以下の公式問題文・個別公式解説の条件を確認して構成した。区間内の最初の出現へ割り当てる数え方は、本文中で対応を示した。

既存の分類・問題配置に対応する出典: