「 今週のお題:『超』整理法に従って並べなおして!」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力 n に対して、次の値を計算して出力する。
- n冊のファイルを横一列に並べる時の全ての並び順に対して「『超』整理法」風に整列し直す時の手数の合計が答えである。
- 「『超』整理法」風の整列とは、選んだファイルを全体の左端に持ってくることで、予め定められたファイル順に、なるべく少ない手数で整列させることを指す。
例として、4冊のファイル CADB を ABCD に整列させる場合、次の図のように2手を要します。
解説
入れ替えの回数が何で決まるか。それは
- ID ( 整列させる時の基準 ) の降順でファイルを追った時、どこで左右の関係が崩れるか
によります。
どういうことか。その前に、手順の中で次の図のようにDを移動したとします。
そうすると、元の配置がどうであったかに関わらず、この後A,B,Cを移動させなければなりません。つまり、Dを移動させる時点で、A,B,C,Dの移動分4手が確定してしまうのです。そのため、最小手順を実現する、ということは、「動かす必要のあるファイルの中でどれが一番後にくるIDか」を決定することに他なりません。
そうすると、
- ABCDEF という並びであれば順序通りなので入れ替え不要 ( 0手 )
- DACEBF という並びであれば、ABの位置とは無関係に、DEF は順序通り、DC は逆順、ということで、C で関係が崩れているため、Cがその「一番後にくるID」 ( C,B,Aと動かして 3手 )
となるわけです ( 次の図も参考に )。
そうすると、「全ての並び順に対して」と考える必要はなくて、ある手数毎に何通りの配置があるか、を計算していけば済むとわかります。
$n$ファイルに対して、移動が $k$ 回 ( $k\ge 1$ ) 必要になる配置は、
- IDの若い方 $k- 1$ ファイルの配置は任意 … ${}_nP_{k- 1}$ 通り
- IDが$k$番目のファイルは、残りの中で先頭以外 … $n-k$ 通り
- 残りは順番通り … 1通り
ということで、$(n-k)\times {}_nP_{k- 1}$ 通りあります。
例えば、$(n,k)=(6,3)$ でA~Fの配置を決める場合は、次の図のようになります。
そのため、$\sum_{k=1}^{n-1}k(n-k)\times {}_nP_{k- 1}$ を計算すれば答えとなります。
実装上は、Σの中身を次のように変形して、かつ k=0 からに範囲を拡張して計算しています。
$$ \begin{eqnarray} & &k(n-k)\times {}_nP_{k- 1} \\ &=&k(n-k)\times \frac{n!}{(n-k+1)!} \\ &=&\frac{k(n-k)\times n!}{(n-k+1)(n-k)\times(n-k- 1)!} \\ &=&\frac{k}{n-k+1}\times\frac{n!}{(n-k- 1)!} \\ &=&\frac{k\times {}_nP_{k+1}}{n-k+1} \end{eqnarray} $$
以下が提出版のRuby(54)です。P の計算結果 ( t ) を累積していって、各iterationで使うようにしています。
n=eval *$< s=0 t=1 n.times{|k|s+=k*(t*=d=n-k)/-~d} p s
終わりに
なかなか規則性に気付かず苦しんだのですが、とても単純な形に落とし込めてスッキリしました。