D - Swap Counter Editorial
by 
n_o_n_o_n
\(f(P)=B\) を満たす \(P\) が存在する必要十分条件は次のようになります．
- 長さ \(N-1\) の数列 \(A\) を \(A_i=B_i+i\;(1 \leq i \leq N-1)\) で定めると以下がともに成り立つ
- \(A\) は広義単調増加列
- \(i=1,2,\dots,N-1\) に対して \(A_i \leq N\)
まずは必要性を示します．
\(f(Q)\) を構築する際の操作を再掲します（これを操作iとします）．
操作 i
- 長さ \(M-1\) の数列 \(X\) を \(0\) で初期化する
- 以下の操作を \(M-1\) 回行う：
- \(i=1,2,\dots,M-1\) の順に以下を行う：
- \(Q_i > Q_{i+1}\) ならば \(Q_i\) と \(Q_{i+1}\) を入れ替え、\(X_i\) に \(1\) を加える
- \(Q_i < Q_{i+1}\) ならば何もしない
これを次のように言い換えます．
操作 ii
- 長さ \(M-1\) の数列 \(X\) を \(0\) で初期化する
- \(i = M, M-1, \dots, 2\) の順に以下の操作を行う:
- 操作の時点で \(Q_j=i\) であるとき \(k=j,j+1,\dots,i-1\) の順に \(Q_k\) と \(Q_{k+1}\) を入れ替え，\(X_k\) に \(1\) を加える
\(2\) つの操作によりできる \(X\) が等しいことは，操作 iにおいて次が成り立つことから従います．
- 全ての \(i=1,2,\dots,M-1\) について 「\(Q_i\) と \(Q_{i+1}\) を入れ替える」という操作を行うときの \(Q_i\) の値は降順
ここで，操作iiにおける
操作の時点で \(Q_j=i\) であるとき \(k=j,j+1,\dots,i-1\) の順に \(X_k\) に \(1\) を加え, \(Q_k\) と \(Q_{k+1}\) を入れ替える
を以下のようにします（操作の終了場所が \(i-1\) → \(N-1\) となっています）．
操作の時点で \(Q_j=i\) であるとき \(k=j,j+1,\dots,N-1\) の順に \(X_k\) に \(1\) を加え, \(Q_k\) と \(Q_{k+1}\) を入れ替える
この書き換えを行うことで \(X_i\) には余計に \(i-1\) だけ値が加算されます．また，操作後に \(Q_1=1\) であるから \(i=1\) についても操作をすることと考えると，これは最初に述べた \(A\) に一致します． 結局，\(A\) は以下の操作 iiiにより生成される数列 \(Y\) と一致することがわかります．
操作 iii
- 長さ \(M-1\) の数列 \(Y\) を \(0\) で初期化する
- \(i=1,2,\dots,M-1\) に対して \(Q_j>Q_i\) なる \(j<i\) の個数を \(C_i\) とする
- \(k=i-C_i\) として \(Y_k,Y_{k+1},\dots,Y_{M-1}\) に \(1\) を加える
これにより，最初に述べた条件が必要であったことが従います．
より詳しく書くとそれぞれ
- 単調増加性:
- \(k \lt N-1\) について \(Y_k\) に値が加算されるとき \(Y_{k+1}\) にも値が加算されることから
- \(A_i \leq N-1\):
- 各 \(i\) について \(Y_i\) への加算の操作が \(N-1\) 回であることから
従います．
次に十分性を示します．
\(A\) の隣接項の差分を見ることで \(k=1,2,\dots,N-1\) について操作 iiiによる \(i-C_i\) の値が \(k\) と一致するものの個数 \(D_k\) が唯一に定まります．このような \(i\) に対する \(P_i\) の集合，\(\lbrace P_i \mid i-C_i=k \rbrace\) を \(S_k\) とします．操作ii において \(Q_j=i\) を満たす \(j\) は \(j \leq i\) を満たすことから \(\forall p \in S_k; p \geq k\) が成立します．逆に，この条件が満たされる \(\lbrace S_k \rbrace_{k=1}^{N-1}\) を一つ定めると，それに対応する順列 \(P\) が一意に定まります．
証明
順列に対して $\lbrace S_k \rbrace_{k=1}^{N-1}$ が存在するのは明らかなので逆の写像の存在を示す． $S_k$ の定義から，$i \lt j$ について $P_i,P_j \in S_k$ について $i-C_i=j-C_j$ なので $C_j-C_i=i-j$ である．すなわち $\forall i \leq l \lt j;P_l \gt P_j$ が必要．逆に $\forall i \leq l \lt j;P_l \gt P_j$ なら $P_i,P_j \in S_k$ であるから，以下のアルゴリズムによって作られる $P$ は条件を満たす．- $T$ を空集合とし，以下を $k=1,2,\dots,N$ の順に行う
- $k \lt N$ ならば $T$ に $S_k$ の要素を全て追加する
- $T$ の最大値を $P_k$ とし，$P_k$ を $T$ から取り除く
以上により十分性が示されました．
最後に，辞書順最小の構築を行いましょう．
先の証明内のアルゴリズムから，\(P_1\) の最小化を達成するには \(S_1=\lbrace 1,2,\dots,D_1 \rbrace\) とする必要があります．次に \(P_2\) について，\(\forall a \in S_1, \forall b \in S_2, a \lt b\) なので \(S_2\) の要素も \(S_1\) の続き番とする必要があります．以降同様に \(N\) までの整数を昇順に追加していくことで辞書順最小化が達成されます．実装の際は stack などを使用することで \(O(N)\) で求めることが出来ます．
posted:
last update: