yukicoder No.1087 転倒数の転倒数

Writer解とは解法が違うらしい。

問題

$N, K$ が与えられます。

次の条件を満たす $N\times N$ の行列 $S$ が存在するか判定し、存在するなら一つ構築しなさい。

$N(N-1)< K$ のときは明らかに不可能です。逆に、これ以外のときは可能です。

以下では、これを実際に構築します。なお、以降では全て0-indexedになります。

突然ですが、$a=\{0, ..., N-1\}$ の順列とし、$S$ を $S_{i, N-1-a_i}=10^6, $ それ以外は $0$ とします。

例えば、$a=[2,1,3,0]$ のときはこんな感じです。

\begin{pmatrix} 0 & 10^6 & 0 & 0 \\ 0 & 0 & 10^6 & 0 \\ 10^6 & 0 & 0 & 0 \\ 0 & 0 & 0 & 10^6 \end{pmatrix}

このとき、$A$ と $B$ は共に $\{0, ..., N-1\}$ の順列になります。

この解法の肝は、このように $S$ を作ると $a$ の転倒数と $A$ の転倒数と $B$ の転倒数が全て等しくなることです。

これは、次のように証明できます。

これによって、$K$ が偶数のときは $a$ の転倒数を $K/2$ にすることで条件を満たす $S$ が構築ができます。

以降では、$K$ は奇数とします。

まずは、$a$ の転倒数が $(K+1)/2$ になるように $a$ を作ります。このとき、$a$ 内の $0$ の位置が $1$ の位置より右に来るように $a$ を作ります。

( $(K+1)/2≧1$ より、数列 $a$ をそういう風に作ることは可能です。)

今度は、$T_{i,j}=i+j$ となる $N\times N$ 行列 $T$ を考えます。

例えば、$N=4$ のときはこんな感じです。

\begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 6 \end{pmatrix}

この $T$ は、どの隣接する $2$ 項を交換しても、それに対応する行または列の転倒数のみが $1$ 増える、という特徴があります。

そして、$S_{i,j}=\max(T_{i,j}, $ さっきまでの $S_{i,j})$ とします。

例えば、$a=[2,1,3,0]$ のときはこんな感じです。

\begin{pmatrix} 0 & 10^6 & 2 & 3 \\ 1 & 2 & 10^6 & 4 \\ 10^6 & 3 & 4 & 5 \\ 3 & 4 & 5 & 10^6 \end{pmatrix}

そして、$a_x=0$ となるような $x$ について、$S_{x,1}$ と $S_{x,2}$ をswapします。

\begin{pmatrix} 0 & 10^6 & 2 & 3 \\ 1 & 2 & 10^6 & 4 \\ 10^6 & 3 & 4 & 5 \\ \color{red}{4} & \color{red}{3} & 5 & 10^6 \end{pmatrix}

こうすると、$B$ は変わらずに、$A$ の $0$ だった項が $1$ になります。

すると、変える前には $A$ 内の $0$ の位置は $1$ の位置より右にあったので、$A$ の転倒数は $1$ 減ります。

変える前の $A$ の転倒数 $+\ B$ の転倒数は $(K+1)/2\times 2=K+1$ だったので、変えた後の $A$ の転倒数 $+\ B$ の転倒数は $K$ となり、条件を満たす $S$ が構築できました。

ただし、このアルゴリズムは $K$ が奇数のときに「$S_{x,1}$ と $S_{x,2}$ は共に $10^6$ ではない」という前提条件を必要としています。

この前提条件は $N≦2$ のときに崩れるので、このアルゴリズムは $N=2,K=1$ で落ちます。

このときだけ場合分けしてやりましょう。例えば、

\begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix}

などです。

解説にすると長いけど、頭の中で解法を整理してる時間はもっと短い。むしろ解法を思いつくまでの時間が長すぎる。

余談：この提出を貼って気がついたけど、yukicoderが500000提出に到達したみたい。おめでとう！