Pythonで最小コストソート(Silly Sort)解いてみた

一週間ほど期間が空きましたが，今日もアルゴリズムの実装をしていきたいと思います．
今回扱う問題は解き方を考えるまでに苦労しますが，実装はそれほど難しくないと思うのでぜひ競技プログラミングが好きな方にはチャレンジしてもらいたい問題になっています．

目次

最小コストソート(Silly Sort)

何の大会かはわかりませんが2002年の世界大会で扱われたこともある問題だそうです．(参考)
問題の内容としては個々の重さwiが定められたn個の荷物を重さの昇順に並び替えた時の最小の移動コストを求めるという問題です．また，荷物の位置の交換は何度でも行うことができます．
対応する問題はALDS1_6_D: Minimum Cost Sortになります．
まずは問題を解いてみたいという方は先に見に行ってみてください.

では，早速問題の中身をみていきたいと思います．
与えられる入出力は

入力 : 一行目に整数nが与えられ，二行目にn個の整数が空白区切りで与えられる.
出力 : 最小コストを出力
制約 : 1 ≦ n ≦ 1000
　　　0 ≦ wi ≦ 10⁴
　　　wiはすべて異なる

となっております．
制限が1秒なのでO(n²)ぐらいまでなら通すことができそうですね．

問題の考察

詳しく問題の内容を紐解いていきたいと思います.
まずは簡単な例を使って問題を図式的にとらえてみようと思います.
例えば，ランダムに並べられた1~8までの重さを持つ荷物の配列{5, 2, 6, 1, 4, 8, 7, 3}が与えられた時の最小コストを考えてみます．
各要素がそれぞれあるべき場所に移動するための矢印を加えたものを図として表しています．

この時，いくつかのサイクルができていることがわかると思います．このループごとに必要な最小コストを求めることを考えると次の図のようにコストは求められます．

よって，最小コストはこの例の場合 "31" となります．
この例ではうまくループの中の最小コストの荷物を利用して要素を移動し，整列させることで最小コストを求めることができました．
しかし，ループに含まれる要素が大きすぎる場合前述の方法では最小のコストを求められない場合があります．
この問題を解消するために，次の2つコスト計算を用いてコストの比較を行います.

1. ループ内の最小の重さの要素を使ってループ内の要素を整列させた時のコスト
2. 全体の要素の中の最小の重さの要素をループの外から持ってきて要素を正しい順序に移動させることによって求めたコスト

この1番目の方法が先ほどの問題例の時の考え方になります.
二番目の方法に関して考えていきたいと思います．
外部から最小の重さの要素を持ってくるには元に戻すことも考慮にいれると
(ループ内の最小の要素)
だけコストが増加します．
また，

だけコストは減少します．

つまり，合計のコストは

となります．
この二つのコストを計算し，値が小さい方を最小の移動コストとして出力することでこの問題を解くことができます．

実装(コード)

では，実際にPythonで実装していきたいと思います.

def solve(w_list, sort_list):
    ans = 0
    min_num = sort_list[0]
    for i in range(len(w_list)):
        x = sort_list.index(w_list[i])
        if x == i:
            continue
        sum_cost = 0
        min_loop_n = 10**4 + 1
        j = i
        loop_count = 0
        while True:
            loop_count += 1 
            sum_cost += w_list[j]
            min_loop_n = min(min_loop_n, w_list[j])
            if x == i:
                break
            w_list[x], w_list[j] = w_list[j], w_list[x]
            x = sort_list.index(w_list[j])
        ans += min(sum_cost + (loop_count-2)*min_loop_n, sum_cost + min_loop_n + (loop_count+1)*min_num)
    return ans
            
n = int(input())
w_list = list(map(int, input().split()))
sort_list = sorted(w_list)
print(solve(w_list, sort_list))
    

最初の図で扱った問題例をsolveにいれてみると，，，

w_list =[5, 2, 6, 1, 4, 8, 7, 3]
sort_list = sorted(w_list)
print(solve(w_list, sort_list))#31

31が出力されると思います．

今回扱かった問題は考え方を思いつくまでに時間がかかりましたが，実装に関しては今までの知識を活用すれば難しくない範囲だったと思います．
気が向いた方は問題の考察の部分を読んで実際に自分で実装してみてください！

もし記事が気に入ってくれた方がいらっしゃったら，コメント・スターよろしくお願いします．