ABC 330 G — Inversion Squared

考察

転倒数を、確定位置同士・未確定位置同士・両者をまたぐ組の三つに分ける。二乗を展開して各項の期待値を求めれば、補完を一つずつ列挙せずに総和を計算できる。ただし、位置を共有する転倒の組は独立ではないため、その依存を数える必要がある。

補完の総和を期待値へ移す

未確定位置の個数を qq とする。補完は q!q! 通りあり、最大 q=3000q=3000 なので全列挙できない。一方、どの補完も同じ重みで足すため、一様に補完したときの平均を求めてから q!q! 倍すればよい。

補完後の順列を PP、その転倒数を II と書く。求めるのは q!E⁡[I2]q!\operatorname{E}[I^2] である。E⁡[I]2\operatorname{E}[I]^2 ではない。二乗は転倒する組を二つ選ぶことに対応し、その二つの組が位置を共有すると、一方の成立が他方の成立しやすさに影響する。

公式解説は転倒する組を、両端が確定・片端だけ確定・両端が未確定の三種類に分け、その組合せを数えている。ここでは同じ分類を使い、未確定部分の転倒数と、各位置への値の割当に伴う寄与へ整理する。以下の分散・条件付き期待値・行列和による導出は、この整理に基づく独自の論証である。

位置の順位と値の順位を分ける

未確定位置の元の添字を k1<k2<⋯<kqk_1<k_2<\cdots<k_q、未使用値を u1<u2<⋯<uqu_1<u_2<\cdots<u_q とする。pp は左から何番目の未確定位置か、vv は小さい方から何番目の未使用値かを表す。どちらも 11 から qq までだが、位置と値という別の対象の順位である。

位置 kpk_p に値 uπpu_{\pi_p} を入れると書けば、π=(π1,…,πq)\pi=(\pi_1,\ldots,\pi_q) は 1,…,q1,\ldots,q の一様ランダム順列になる。実際の値の大小と順位の大小は一致する。

転倒数を次の三つに分ける。

  • aa:両端が確定している組の転倒数。補完によらない定数である。
  • UU:両端が未確定の組の転倒数。π\pi 自身の転倒数に等しい。
  • BB:片端だけが未確定の組の転倒数。

BB を位置ごとの和にするため、未確定位置 kpk_p に値 uvu_v を置いたとき、確定値との間にできる転倒数を wp,vw_{p,v} と定める。

wp,v=#{i<kp:Ai≠−1, Ai>uv}+#{i>kp:Ai≠−1, Ai<uv}.\begin{aligned} w_{p,v}={}&\#\{i<k_p:A_i\ne-1,\ A_i>u_v\}\\ &+\#\{i>k_p:A_i\ne-1,\ A_i<u_v\}. \end{aligned}

ここで #\# は集合の要素数である。左の確定値は割り当てる値より大きいとき、右の確定値は小さいときに転倒する。この重み表を使うと、

U=∑1≤p<r≤q1[πp>πr],B=∑p=1qwp,πp,I=a+U+B.\begin{aligned} U&=\sum_{1\leq p<r\leq q}\mathbf{1}[\pi_p>\pi_r],\\ B&=\sum_{p=1}^q w_{p,\pi_p},\\ I&=a+U+B. \end{aligned}

となる。1[条件]\mathbf{1}[\text{条件}] は、条件が成り立つとき 11、それ以外は 00 である。

例えば A=(3,−1,2,−1)A=(3,-1,2,-1) では、未確定位置は (k1,k2)=(2,4)(k_1,k_2)=(2,4)、未使用値は (u1,u2)=(1,4)(u_1,u_2)=(1,4) であり、確定した 3>23>2 により a=1a=1 となる。

未確定位置v=1v=1(値 11)v=2v=2(値 44)
p=1p=1(位置 22)w1,1=1w_{1,1}=1w1,2=1w_{1,2}=1
p=2p=2(位置 44)w2,1=2w_{2,1}=2w2,2=0w_{2,2}=0

位置 22 に 44 を置く場合は右の 22 と転倒し、位置 44 に 11 を置く場合は左の 3,23,2 と転倒する。表の行が位置、列が値であることに注意する。

順位の割当 π\pi補完後の PPaaUUBBII
(1,2)(1,2)(3,1,2,4)(3,1,2,4)11001+0=11+0=122
(2,1)(2,1)(3,4,2,1)(3,4,2,1)11111+2=31+2=355

三分解のどこにも漏れや重複はない。二つの位置が確定か未確定かで、各転倒は必ず一種類に属するからである。

二乗を展開し、必要な量を絞る

aa は定数なので、二乗を展開すると

E⁡[I2]=a2+E⁡[U2]+E⁡[B2]+2a(E⁡[U]+E⁡[B])+2E⁡[UB].\begin{aligned} \operatorname{E}[I^2]={}&a^2+\operatorname{E}[U^2]+\operatorname{E}[B^2]\\ &+2a\bigl(\operatorname{E}[U]+\operatorname{E}[B]\bigr) +2\operatorname{E}[UB]. \end{aligned}

以降は、未確定部分だけで決まる E⁡[U],E⁡[U2]\operatorname{E}[U],\operatorname{E}[U^2]、依存を扱う E⁡[UB]\operatorname{E}[UB]、重み表から得る E⁡[B],E⁡[B2]\operatorname{E}[B],\operatorname{E}[B^2] を順に求める。UU と BB は独立とは限らない。小例でも U=1U=1 の補完で BB が大きいため、E⁡[UB]\operatorname{E}[UB] を期待値の積で代用できない。

まず q=0q=0 なら補完は一つで答えは a2a^2。q=1q=1 なら未確定同士の組はなく、唯一の割当によって答えは (a+w1,1)2(a+w_{1,1})^2 と決まる。以下では q≥2q\geq2 とする。二項係数 (nr)\binom{n}{r} は n<rn<r のとき 00 と扱う。

未確定部分の二次モーメントを求める

二次モーメントとは、二乗の期待値のことである。UU については、各転倒の起こりやすさと、二つの転倒の依存を分けて求める。Xp,r=1[πp>πr]X_{p,r}=\mathbf{1}[\pi_p>\pi_r] と置くと、各組は確率 1/21/2 で転倒するので、

E⁡[U]=(q2)2=q(q−1)4,Var⁡(Xp,r)=14.\operatorname{E}[U]=\frac{\binom{q}{2}}{2}=\frac{q(q-1)}4, \qquad \operatorname{Var}(X_{p,r})=\frac14.

分散 Var⁡(X)=E⁡[X2]−E⁡[X]2\operatorname{Var}(X)=\operatorname{E}[X^2]-\operatorname{E}[X]^2 と、共分散 Cov⁡(X,Y)=E⁡[XY]−E⁡[X]E⁡[Y]\operatorname{Cov}(X,Y)=\operatorname{E}[XY]-\operatorname{E}[X]\operatorname{E}[Y] を使う。

四つの異なる位置からなる二つの組では、それぞれの組の両端の値を交換することで、大小関係の四通りが一対一に対応する。したがって同時に転倒する確率は 1/41/4、共分散は 00 である。これは転倒の大小関係の独立性であり、各位置への値の割当自体が独立という意味ではない。

一つの位置を共有する場合は、三位置 i<j<ki<j<k の相対順 66 通りを調べればよい。

二つの指示変数同時に転倒する条件同時成立確率共分散
Xi,j,Xi,kX_{i,j},X_{i,k}πi\pi_i が三つで最大1/31/31/3−1/4=1/121/3-1/4=1/12
Xi,j,Xj,kX_{i,j},X_{j,k}πi>πj>πk\pi_i>\pi_j>\pi_k1/61/61/6−1/4=−1/121/6-1/4=-1/12
Xi,k,Xj,kX_{i,k},X_{j,k}πk\pi_k が三つで最小1/31/31/3−1/4=1/121/3-1/4=1/12

三位置あたりの共分散の和は 1/121/12 である。和の分散では、異なる二項を選ぶ順序を入れ替えた分も含むので、この和に 22 を掛ける。同じ組を二回選ぶ分は各指示変数の分散で既に数えている。よって

Var⁡(U)=(q2)4+2(q3)112=q(q−1)(2q+5)72,E⁡[U2]=Var⁡(U)+E⁡[U]2.\begin{aligned} \operatorname{Var}(U) &=\frac{\binom{q}{2}}4+2\binom{q}{3}\frac1{12}\\ &=\frac{q(q-1)(2q+5)}{72},\\ \operatorname{E}[U^2] &=\operatorname{Var}(U)+\operatorname{E}[U]^2. \end{aligned}

ここでは二つの組が同一・一位置を共有・位置を共有しない、という全場合を尽くしている。

一つの割当を固定して交差項を求める

UBUB を直接展開すると、転倒の組と、位置・値の割当を同時に追うことになる。そこで BB の一項に注目し、先に πp=v\pi_p=v を固定する。残る q−1q-1 個の値は残る位置に一様に割り当てられる。

この条件の下での UU の期待値を Hp,v=E⁡[U∣πp=v]H_{p,v}=\operatorname{E}[U\mid\pi_p=v] とする。pp を含まない組では、残る二値の大小は対称なので転倒確率が 1/21/2 である。pp を含む組では、左右で転倒条件が異なる。

転倒を調べる組組の個数一組の転倒確率
pp を含まない(q−12)\binom{q-1}{2}1/21/2
pp より前と ppp−1p-1q−vq−1\dfrac{q-v}{q-1}
pp と pp より後q−pq-pv−1q−1\dfrac{v-1}{q-1}

前の位置と転倒するには値の順位が vv より大きくなければならず、候補は q−vq-v 個ある。後の位置と転倒するには小さくなければならず、候補は v−1v-1 個ある。従って

Hp,v=(q−12)2+(p−1)(q−v)+(q−p)(v−1)q−1.H_{p,v}=\frac{\binom{q-1}{2}}2 +\frac{(p-1)(q-v)+(q-p)(v-1)}{q-1}.

各割当 πp=v\pi_p=v の確率は 1/q1/q である。この条件の下では重みが wp,vw_{p,v} に決まるので、

E⁡[UB]=∑p=1qE⁡[Uwp,πp]=1q∑p=1q∑v=1qwp,vHp,v.\begin{aligned} \operatorname{E}[UB] &=\sum_{p=1}^q\operatorname{E}[U w_{p,\pi_p}]\\ &=\frac1q\sum_{p=1}^q\sum_{v=1}^q w_{p,v}H_{p,v}. \end{aligned}

この計算では UU と BB の独立性を仮定していない。小例の q=2q=2 では π=(2,1)\pi=(2,1) のときだけ U=1U=1 なので、E⁡[UB]=(w1,2+w2,1)/2=3/2\operatorname{E}[UB]=(w_{1,2}+w_{2,1})/2=3/2 となる。期待値の積は E⁡[U]E⁡[B]=(1/2)⋅2=1\operatorname{E}[U]\operatorname{E}[B]=(1/2)\cdot2=1 であり、異なることも確認できる。

重み表の行・列から割当費用の二次モーメントを求める

重み表の行和・列和・全和・二乗和を定義する。

Rp=∑v=1qwp,v,Cv=∑p=1qwp,v,S=∑p=1q∑v=1qwp,v,W2=∑p=1q∑v=1qwp,v2.\begin{aligned} R_p&=\sum_{v=1}^q w_{p,v},& C_v&=\sum_{p=1}^q w_{p,v},\\ S&=\sum_{p=1}^q\sum_{v=1}^q w_{p,v},& W_2&=\sum_{p=1}^q\sum_{v=1}^q w_{p,v}^2. \end{aligned}

一位置への各値の割当確率は 1/q1/q だから、E⁡[B]=S/q\operatorname{E}[B]=S/q である。二乗については、同じ位置の寄与を二回選ぶ場合と、異なる位置を選ぶ場合を分ける。

B2=∑p=1qwp,πp2+∑1≤p,r≤qp≠rwp,πpwr,πr.B^2=\sum_{p=1}^q w_{p,\pi_p}^2 +\sum_{\substack{1\leq p,r\leq q\\p\ne r}}w_{p,\pi_p}w_{r,\pi_r}.

第一項の期待値は W2/qW_2/q となる。第二項では、異なる位置に同じ値を割り当てられないため、p≠rp\ne r に加えて v≠sv\ne s が必要である。そのような二つの割当の同時成立確率は

Pr⁡(πp=v, πr=s)=(q−2)!q!=1q(q−1).\Pr(\pi_p=v,\ \pi_r=s)=\frac{(q-2)!}{q!}=\frac1{q(q-1)}.

残る課題は、異なる行・異なる列から選ぶ二つの重みの積和を、全四添字を列挙せずに求めることである。

まず S2S^2 は表の二つのマスを順序付きで選ぶ全積和である。ここから同じ行を選んだ分 ∑pRp2\sum_p R_p^2 と同じ列を選んだ分 ∑vCv2\sum_v C_v^2 を引く。同じマスを二回選ぶ分は二重に引いたので、W2W_2 を一回戻す。包除により

∑1≤p,r≤qp≠r∑1≤v,s≤qv≠swp,vwr,s=S2−∑p=1qRp2−∑v=1qCv2+W2.\begin{aligned} &\sum_{\substack{1\leq p,r\leq q\\p\ne r}} \sum_{\substack{1\leq v,s\leq q\\v\ne s}}w_{p,v}w_{r,s} \\ &\quad=S^2-\sum_{p=1}^q R_p^2-\sum_{v=1}^q C_v^2+W_2. \end{aligned}

従って

E⁡[B2]=W2q+S2−∑pRp2−∑vCv2+W2q(q−1).\operatorname{E}[B^2]=\frac{W_2}{q} +\frac{S^2-\sum_p R_p^2-\sum_v C_v^2+W_2}{q(q-1)}.

ここは最初から順序付きの組で数えている。p<rp<r の組を数えた式ではないため、さらに 22 倍してはいけない。

小例の表では、行和は (2,2)(2,2)、列和は (3,1)(3,1)、S=4,W2=6S=4,W_2=6 である。異なる行・列の積和は 16−8−10+6=416-8-10+6=4 となり、

E⁡[B2]=62+42⋅1=5\operatorname{E}[B^2]=\frac62+\frac4{2\cdot1}=5

を得る。実際の二補完の平均 (12+32)/2=5(1^2+3^2)/2=5 と一致する。

重み表を作り、全体の答えへ戻す

重み一つの計算で確定位置を走査すると、表全体で三重ループになってしまう。位置と値の累積個数を先に求める。

元の位置 kk と閾値 0≤t≤N0\leq t\leq N について、Lk(t)L_k(t) を「kk より左にある tt 以下の確定値の個数」、Dk(t)D_k(t) を「kk より右にある tt 以下の確定値の個数」と定義する。すると

wp,v=Lkp(N)−Lkp(uv)+Dkp(uv−1)w_{p,v}=L_{k_p}(N)-L_{k_p}(u_v)+D_{k_p}(u_v-1)

で一マスを定数時間で得られる。Lk(N)−Lk(uv)L_k(N)-L_k(u_v) が左の大きい値、Dk(uv−1)D_k(u_v-1) が右の小さい値を数える。

累積個数の表は、閾値 tt を一つ固定して左右から走査すれば作れる。左の表は L1(t)=0L_1(t)=0 から始め、kk を通過するとき、Ak≠−1A_k\ne-1 かつ Ak≤tA_k\leq t なら個数に 11 を加えて Lk+1(t)L_{k+1}(t) とする。右の表は DN(t)=0D_N(t)=0 から逆向きに同じ処理をする。全閾値を処理しても O(N2)O(N^2) である。

全体の処理順は次のとおり。

  1. 未確定位置と未使用値を昇順に取り出す。確定位置の二つ組を調べ、aa を数える。
  2. q=0q=0 なら a2a^2 を返す。q=1q=1 なら唯一の未確定位置と全確定位置を比較して w1,1w_{1,1} を求め、(a+w1,1)2(a+w_{1,1})^2 を返す。
  3. L,DL,D の表を作る。全 q2q^2 個の wp,vw_{p,v} を求め、初期値をすべて 00 とした Rp,Cv,S,W2R_p,C_v,S,W_2 と、交差項用の和 T=∑p,vwp,vHp,vT=\sum_{p,v}w_{p,v}H_{p,v} を加算する。
  4. E⁡[U],E⁡[U2]\operatorname{E}[U],\operatorname{E}[U^2]、E⁡[UB]=T/q\operatorname{E}[UB]=T/q、E⁡[B],E⁡[B2]\operatorname{E}[B],\operatorname{E}[B^2] を求め、二乗の展開式へ代入する。
  5. 最後に q!q! を掛け、補完すべての二乗総和へ戻す。

導出では通常の有理数として期待値を扱ったが、実装は法 998244353998244353 上で行う。分母は逆元に置き換える。2,4,72,q,q−12,4,72,q,q-1 は、この分岐と制約の下ではすべて法と互いに素である。必要な逆元はループ前に求めればよい。

小例では a=1a=1、E⁡[U]=E⁡[U2]=1/2\operatorname{E}[U]=\operatorname{E}[U^2]=1/2、E⁡[B]=2\operatorname{E}[B]=2、E⁡[B2]=5\operatorname{E}[B^2]=5、E⁡[UB]=3/2\operatorname{E}[UB]=3/2 なので、

E⁡[I2]=1+12+5+2(12+2)+2⋅32=292.\operatorname{E}[I^2] =1+\frac12+5+2\left(\frac12+2\right)+2\cdot\frac32 =\frac{29}2.

補完数 2!=22!=2 を掛けると 29=22+5229=2^2+5^2 となり、直接数えた答えと一致する。

典型の発動条件

indicator積への展開

個数の二乗総和を求めるときは、「条件を満たす対象を順序付きで二つ選ぶ」と読み替える。同じ対象を二回選ぶ場合も含む。対象同士の重なり方で同時成立確率が変わるため、単なる期待値の二乗では足りない。

一様ランダム順列のmoment

未使用値を未確定位置へ一対一に割り当てる全補完を集計するときは、一様ランダム順列の期待値に補完数を掛けられる。転倒数のように相対的な大小だけで決まる量は、実際の値を順位に置き換えると共通の式で扱える。

条件付き期待値でcross term計算

順列全体の統計量と、各位置への割当費用の積が現れたときは、一つの位置への値を固定してみる。固定後の残りが一様順列なら、全体の統計量を「その位置を使う部分」と「使わない部分」に分けて期待値を求められる。

without-replacementな二次和の集約

値を重複なく割り当てた費用の二次モーメントでは、同じ位置と同じ値を選ぶ項の扱いが鍵になる。全マスの積和から同じ行・同じ列を包除すると、異なる位置への異なる値の割当を、行和・列和・二乗和だけで集計できる。

問題固有の要素

未確定位置だけを見ると転倒数は順位順列だけで決まり、確定値をまたぐ転倒は位置と値の重み表に押し込められる。この二つの異なる構造を UU と BB に分けることで、細かい場合分けが必要な依存を UBUB の条件付き期待値へ集約した。

初見では、二つの転倒の全四位置を追い始める前に、「補完によらない部分」「順位の相対順だけで決まる部分」「一つの割当で決まる部分」を探す。この分離ができれば、各部分に適した集計方法を選べる。

正当性

各補完は、未確定位置と未使用値の順位の間の全単射に一意に対応する。両端の確定状況で各転倒を分類すると、定数 aa、順位順列の転倒数 UU、割当費用 BB のいずれかに一度だけ含まれるため、I=a+U+BI=a+U+B が成り立つ。

UU の分散の導出は、二つの転倒の組が同一・一位置を共有・位置を共有しない場合を尽くしている。UBUB の計算は、一つの割当を固定した下で、転倒の組がその位置を使うかどうかを分けており、独立性を仮定せず全寄与を足している。

B2B^2 では同じ位置の二乗を別に数え、異なる位置については同じ値の割当を除いている。行と列の包除は、両方が異なる順序付きのマスの組をちょうど一回ずつ残す。各割当の成立確率を掛けることで、二乗の全項の期待値が得られる。

従って二乗の展開式にはすべての対角項・交差項が正しい係数で含まれ、得られる量は E⁡[I2]\operatorname{E}[I^2] である。全 q!q! 個の補完が等確率なので、q!q! 倍すれば求める総和になる。q=0,1q=0,1 は唯一の補完を直接計算する分岐で正しい値を返す。

実装上の注意

  • pp は未確定位置の順位、kpk_p は元の位置、vv は未使用値の順位、uvu_v は実際の値である。Hp,vH_{p,v} には順位を、累積個数の参照には元の位置と実際の値を使う。
  • q=0,1q=0,1 は、qq や q−1q-1 の逆元を求める前に分岐する。存在しない二位置への割当を分母ゼロの式で評価しない。
  • S2−∑pRp2−∑vCv2+W2S^2-\sum_p R_p^2-\sum_v C_v^2+W_2 は順序付きの積和であり、追加の二倍は不要である。一方、I2I^2 の展開に現れる 2E⁡[UB]2\operatorname{E}[UB] の係数は必要である。
  • 行和・列和・二乗和・交差項の和は逐次法を取る。例えば SS は最大で q2(N−q)q^2(N-q) に達し得るため、整数のまま S2S^2 を作ると64 bitに収まらない。法を取った値同士の積には64 bit整数を使い、包除の減算結果は非負の剰余へ直す。
  • (q−12)\binom{q-1}{2} などは整数の式として評価してから法を取ってもよい。最終的な期待値から総和へ戻す q!q! を掛け忘れない。

復習の核

  • 二乗の平均を求めるときは、同じ対象・重なる対象・離れた対象の寄与を区別する。離れた位置の大小関係が独立でも、値の割当全体は独立ではない。
  • 全体の統計量と位置別費用の積には、一つの割当で条件付ける。残りの対称性が使えるかを確かめる。
  • 重複を許さない二割当の和は、全積和から同じ行・同じ列を包除する。順序付きかどうかを決めてから係数を付ける。
  • 二つの補完だけでも交差項の欠落を検出できる。q=2q=2 で直接計算し、q=0,1q=0,1 では分母を使う前の分岐を確認する。

計算量と制約

時間

O(N2)O(N^2)。未確定位置・未使用値の抽出と階乗は O(N)O(N)、確定位置同士の転倒数と左右の累積個数表は O(N2)O(N^2) で求まる。重み表と行和・列和・二乗和・条件付き期待値の積和は全 q2q^2 マスを一度ずつ処理するので O(q2)O(q^2)。逆元は必要な定数個だけループ前に求め、各マスで累乗しない。

空間

O(N2)O(N^2)。左右の累積個数表が O(N2)O(N^2)、重み表が O(q2)O(q^2)、行和・列和と位置・値の一覧が O(N)O(N) を使う。重みは一マスずつ集計して保存を省けるが、累積個数表を保持するこの手順全体の評価は変わらない。

制約との対応

1≤N≤30001\leq N\leq3000 なので、O(N2)O(N^2) の走査で全位置・値の組を扱える。値が 1,…,N1,\ldots,N の範囲にあり重複しないため、未使用値の昇順抽出と順位化が可能である。全要素が未確定なら a=B=0a=B=0 となり、式は q!E⁡[U2]q!\operatorname{E}[U^2] に帰着する。全要素が確定なら q=0q=0 の分岐になる。法 998244353998244353 は素数で NN より大きく、分岐後に使うすべての分母の逆元が存在する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Inversion Squared の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 寄与の数え上げと順序交換

    補助タグ: 法上の四則演算・高速累乗・逆元 累積和・差分配列

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

    この解説で扱わないこと:

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

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題