Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の6_D問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#6「ソート」では、実用的なソートアルゴリズムについて紹介します。
問題（6_D: Minimum Cost Sort）
問題はリンク先をご覧ください。
AOJ ALDS1 6_D問題: Minimum Cost Sort
頂点を巡回するグループに分けて交換する値を計算します。
解説
いくつかの例で実際に値を計算します。
例1）（問題の入力例1です）
1 5 3 4 2
5 と 2 を入れ替えて 7 となります。5→2→5の巡回となっています。
例2）3個以上の巡回がある場合を考えます。
2 4 1 3（2→4→3→1→2の巡回となっています）
3 と 1 を入れ替えます（コスト4）。2 4 3 1 となります。次に 4 と 1 を入れ替えます（コスト5）。2 1 3 4 となります。次に 2 と 1 を入れ替えます（コスト3）。合計で12となります。
ここまでをまとめると、同じ巡回に含まれている値（$w_1, \cdots, w_n$）の最小値を $t_{min}$ とすると、以下の式でこの巡回を並び替えるコストが求まる気がします（また、この式は、$n$ が2の場合も成立しています）。
$$(1) \; \sum_{w_i \neq t_{min}} (w_i + t_{min}) = \sum w_i + (n-2) \times t_{min}$$
最小値が小さい場合は成り立たない。
ただし、以下の場合は正しくありません。
1 12 14 11 13
後半4つを入れ替えるコストは、上記の式に従うと 50 + 2 × 11 = 72 となります。
この数列の1と11を入れ替えます。以下となります。
11 12 14 1 13
後半4つを入れ替えるコストは、40 + 2 × 1 = 42 となります。この後に1と11を入れ替えます。この場合、1と11を往復入れ替えるコスト (1+11) × 2 = 24 を42に加えた66の方がコストは少なくなります。つまり全体の最小値を$w_{min}$とすると、増えるコスト $(t_{min}+w_{min})\times 2$ となり、減るコスト $(n-1)\times(t_{min}-w_{min})$ となります。結果的に
$$(2) \; \sum w_i + (n-2) \times t_{min} + (t_{min}+w_{min})\times 2\; -\; (n-1)\times(t_{min}-w_{min})$$
$$= \sum w_i + t_{min} + (n+1) \times w_{min}$$
となります。巡回するグループ毎に式(1)と式(2)の最小値をコストとして加えていきます。
C++ プログラム例（ALDS1 6_D）
上記の考察に従いコストを計算します。
- 元のデータ w とは別にソートしたデータを a として持ちます。配列 position として、ソート後の場所を持ちます。
- その頂点を調べたかを bool 配列 seen で管理します。
- 巡回しているグループ毎に上記で求めた式の値を計算します。計算結果を変数 result に加えていきます。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_W 10000
int main()
{
int n;
cin >> n;
vector<int> w(n);
vector<int> a(n);
int min_w = MAX_W + 1;
for (int i = 0; i < n; ++i) {
cin >> w[i];
a[i] = w[i];
min_w = min(min_w, w[i]);
}
sort(a.begin(), a.end());
vector<int> position(MAX_W + 1, -1);
vector<bool> seen(n, false);
for (int i = 0; i < n; ++i) {
position[a[i]] = i;
}
int result = 0;
for (int i = 0; i < n; ++i) {
if (seen[i]) {
continue;
}
if (a[i] == w[i]) {
seen[i] = true;
continue;
}
int cur = i;
int t_num = 0;
int t_sum = 0;
int t_min = MAX_W + 1;
while (true) {
seen[cur] = true;
++t_num;
int v = w[cur];
t_sum += v;
t_min = min(t_min, v);
cur = position[v];
if (seen[cur]) {
break;
}
}
result += min(t_sum + (t_num - 2) * t_min,
t_sum + t_min + (t_num + 1) * min_w);
}
cout << result << endl;
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
頂点を巡回するグループに分けて計算しましたが、気づきにくい場合分けが必要でした。このような問題が実際にコンテストで解けると、楽しくなると思います。
引き続き、ALDS1 の問題を紹介していきます。
