Codeforces Round #347 (Div. 1) E. Binary Table

かなり面倒なことをしてたら解けたので書いておきます。

解法

行列を縦読みしたとき現れるビット列 i の頻度を x[i]、ビット列 i に対し y[i]=min(popcount(i), n-popcount(i)) とする。

行反転を行わなわず、列反転のみを行った際の最小値は次のように表せる。

$$ z[0]=x[0]y[0]+x[1]y[1]+x[2]y[2]+\cdots+x[2^n -1]y[2^n -1] $$

反転させる行をビットマスクで表現したものを k としたときの最小値は次のようになる。

$$ z[k]=x[0]y[0 \oplus k]+x[1]y[1 \oplus k]+x[2]y[2 \oplus k]+ \cdots + x[2^n-1]y[(2^n-1) \oplus k] $$

これを全ての k に対して求めてあげると、

$$ \begin{bmatrix} z[0] \\ z[1] \\ \vdots \\ z[N-1] \end{bmatrix}=A \begin{bmatrix} x[0] \\ x[1] \\ \vdots \\ x[N-1] \end{bmatrix} $$

のように書ける。z の最小値が答えだ。A の次元が 2²⁰ 程度なので、愚直に掛け算をしたら間に合わない。A にいい性質がないだろうか。

よく観察すると A は以下の様な再帰的な構造をしていることがわかる。

$$ A=\begin{bmatrix} X & Y \\ Y & X \\ \end{bmatrix} $$

ところで以下の等式が成り立つ。

$$ \begin{bmatrix} a & b \\ b & a \end{bmatrix}=\frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}\begin{bmatrix} a+b & 0 \\ 0 & a-b \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} $$

X=[[a,b],[b,a]], S=[[1,1],[1,-1]], J=[[a+b,0],[0,a-b]] と置くと、X=SJS/2 と表せる。

Y=[[c,d],[d,c]] とすると次も成り立つ。ただし J(X) と書いたら X の Jordan 標準形とし、S は X=SJ(X)S/2 を満たす行列とする。

$$ \begin{bmatrix} X & Y \\ Y & X \end{bmatrix}=\frac{1}{2^2}\begin{bmatrix} S & S \\ S & -S \\ \end{bmatrix}\begin{bmatrix} J(X)+J(Y) & O \\ O & J(X)-J(Y) \end{bmatrix}\begin{bmatrix} S & S \\ S & -S \\ \end{bmatrix} $$

これを何回も繰り返すことで A の Jordan 標準形および標準化する行列 S が求められる。さらに求める作業の逆を行うことで A=SJSx /2ⁿ をO(N log N) で求めることができる。

---

Jordan 標準形は以下の漸化式で計算すればいい。

$$ J\left(\begin{bmatrix} X & Y \\ Y & X \end{bmatrix}\right)=\begin{bmatrix} J(X)+J(Y) & O \\ O & J(X)-J(Y) \end{bmatrix} $$

サイズ n のときの計算時間を T(n) とすると、T(n)=2T(n/2)+O(n) なので T(n)=O(n log n) となる。

サイズ 2ⁿ のときの標準化する行列を Sn と書くことにすると次が成り立つ。

$$ S_n=\begin{bmatrix} S_{n-1} & S_{n-1} \\ S_{n-1} & -S_{n-1} \end{bmatrix} $$

よって Sn x は以下のように再帰的に計算できる。

$$ S_n \mathbb{x} = \begin{bmatrix} S_{n-1} & S_{n-1} \\ S_{n-1} & -S_{n-1} \end{bmatrix}=\begin{bmatrix} \mathbb{x}_0 \\ \mathbb{x}_1 \\ \end{bmatrix} $$

これは S[n-1] x0 と S[n-1] x1 を計算してマージすればいいので O(n log n) でできる。

よって全体の計算量は O(N log N)。最後に 2ⁿ で割るのを忘れないように。

Codeforces Round #347 (Div. 1) E. Binary Table

本番中は行列まで作って諦めていたのだが、対角化を試してみたら不思議と解けた。[[A,B],[B,A]] の形をした行列全般に使えそう。ところで computeJ と mulS が全く同じコードになってて面白い。