\(P_{Q_i}=i\) が成り立つ順列 \(Q\) を考えます。

操作を逆からみると順列 \((1,2,3,\dots,N)\) に対して「いくつかの項を順序を保ったまま末尾へもっていく」という操作を行うことで、順列を \(Q\) に変換する際の最小コストをもとめる問題になります。

「いくつかの項を順序を保ったまま末尾へもっていく」という操作は基数 \(B=2\) の基数ソートと同じ挙動になっています。このことをもうすこし厳密に述べしょう。非負整数列 \(X=(X_1,X_2,\dots,X_N)\) を用意します。はじめ \(X_i=0\ (1\leq i \leq N)\) です。 \(k\) 回目の操作で整数 \(i\) を末尾に持って行ったとき、\(X_i\) を \(X_i+2^k\) で置き換えます。 \(K\) 回の操作を終えた後、最終的に得られる順列は \(i\ (1\leq i \leq N)\) を \(X_i\) の昇順に安定ソートしたものになっています。すると順列 \(Q\) を得るには \(Q_i < Q_{i+1}\) ならば \(X_i \leq X_{i+1},\) \(Q_{i} > Q_{i+1}\) ならば \(X_i < X_{i+1}\) が成り立つように一連の操作を行うことが必要十分です。

よって問題は以下のように言い換えられます。

\(2^K\) 未満の非負整数 \(n\) の二進法表記 \(n=\sum_{i=1}^{m}2^{k_i}\) に対し、\(f(n)=\sum_{i=1}^{m}C_{K-k_i}\) とする。

以下の条件を満たす長さ \(N\) の単調非減少の非負整数列 \(X\) に対する \(\sum_{i=1}^{N}f(X_i)\) の最小値を求めよ。

• \(Q_{i} > Q_{i+1}\) ならば \(X_i < X_{i+1}\)
• \(X_N < 2^K\)

これは \(2^{k} \leq X_i\) となる最小の \(i\) を決め打つ区間dpで計算でき、\(O(KN^3)\) で求めることができます。