「 今週のお題:『超』整理法に従って並べなおして!」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力 n に対して、次の値を計算して出力する。
  • n冊のファイルを横一列に並べる時の全ての並び順に対して「『超』整理法」風に整列し直す時の手数の合計が答えである。
  • 「『超』整理法」風の整列とは、選んだファイルを全体の左端に持ってくることで、予め定められたファイル順に、なるべく少ない手数で整列させることを指す。

例として、4冊のファイル CADB を ABCD に整列させる場合、次の図のように2手を要します。

f:id:ange1:20160309191143p:plain

解説

入れ替えの回数が何で決まるか。それは

  • ID ( 整列させる時の基準 ) の降順でファイルを追った時、どこで左右の関係が崩れるか

によります。

どういうことか。その前に、手順の中で次の図のようにDを移動したとします。

f:id:ange1:20160309192318p:plain

そうすると、元の配置がどうであったかに関わらず、この後A,B,Cを移動させなければなりません。つまり、Dを移動させる時点で、A,B,C,Dの移動分4手が確定してしまうのです。そのため、最小手順を実現する、ということは、「動かす必要のあるファイルの中でどれが一番後にくるIDか」を決定することに他なりません。

そうすると、

  • ABCDEF という並びであれば順序通りなので入れ替え不要 ( 0手 )
  • DACEBF という並びであれば、ABの位置とは無関係に、DEF は順序通り、DC は逆順、ということで、C で関係が崩れているため、Cがその「一番後にくるID」 ( C,B,Aと動かして 3手 )

となるわけです ( 次の図も参考に )。

f:id:ange1:20160309194804p:plain

そうすると、「全ての並び順に対して」と考える必要はなくて、ある手数毎に何通りの配置があるか、を計算していけば済むとわかります。

$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の配置を決める場合は、次の図のようになります。

f:id:ange1:20160309203912p:plain

そのため、$\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

終わりに

なかなか規則性に気付かず苦しんだのですが、とても単純な形に落とし込めてスッキリしました。