アルゴリズムとデータ構造入門
当記事について
Aizu Online Judgeに掲載されている問題をC++で解くという遊びをしているので、考え方の例と解けたコード例を記録していこうかと思います。コード例はたたんでおこうかと思います。クリックやタップでコード例を開けます。
問題のリンクはこの辺りになります:
この問題は難易度の高い応用問題です。
ということで、今回は結構むずかしめ。
ALDS1_6_D: Minimum Cost Sort: 最小コストソート
横一列に並んだ重さの異なる荷物を重さの順に並び替える問題。並べ替えはロボットアームによる入れ替えで行い、入れ替えには入れ替える荷物の重量の和のコストがかかる、という想定です。
与えられるのは、荷物の個数 $n \space (1 \leq n \leq 1000)$ と、各荷物の重量 $0 \leq w_i \leq 10^4 \space (i \in {\{0,2,3,...,n-1\}})$ の合計 $n+1$ 個の値です。
考えたこと
ひとまず、荷物の重量の配列を $W$ とします。その要素の $w_i$ と $w_j$ などの交換を繰り返します。
動かし方の考え
無作為に動かすと合計コストが増えるだけなので、動かすときは、2つのうちどちらかをあるべき場所に配置できるように動かす必要がありそうです。またこのとき、重量が小さいものを繰り返し動かしたほうが、総和は小さくなりそうだなと感覚的に思います。
よって、まずは荷物のあるべき場所を知るためにソート済みの配列 $A$ を用意する必要があります。
具体的な配列で考える
具体的な数列で考えてみます。
6個くらいの数をランダムに並べて、それに対応するソート済み配列と一緒に、
$$W = [16, 4, 19, 15, 8, 18]$$ $$A = [4, 8, 15, 16, 18, 19]$$
のように上下に並べてみます。ここでは、添字を0ベースとして考えます。$w_0=16$であり、$a_1=8$です。
$A$ の最初から順番にあるべき数字と、 $W$ での位置の現状の数字を見ると、 $4$ があるべきところに $16$ があります。そこで $16$ を適切な位置に動かそうと思って $A$ の $16$ の位置( $a_3$ )に対応する $w_3$ を見ると、今度は $15$ があります。そこで $15$ を適切な……と繰り返していき、動かしたいものを並べていくと、
$$ 16 \text{--} 15 \text{--} 19 \text{--} 18 \text{--} 8 \text{--} 4 \text{--} 16 $$
のように繋がっているように見えると思います。輪のようになります。これをグループと呼ぶことにします。
この例では、配列全体で、1つのグループになっていますが、値の配置の仕方によっては複数のグループになります。 グループの数は $n$ 個が最大で、整列済みの配列が与えられた場合です。
複数グループの場合は、例えば
$$ W = [4, 1, 7, 3, 6, 8] $$ $$ A = [1, 3, 4, 6, 7, 8] $$
であれば、 $4 \text{--} 7 \text{--} 6 \text{--} 3 \text{--} 1 \text{--} 4$ と、 $8 \text{--} 8$ の2グループに分けられます。グループ内の数字が2種類以上であればソートが必要になりますね。そして、このグループ内のソートをする時に、動かし方の考えのところで述べた小さい値を何回も入れ替えに使うという方法でコストを計算します。
グループ内での入れ替えコスト
上の2つのグループに分けた例を使うと、 $4,7,6,3,1$ のソートになります。このグループ内での並べ替えが基本となり、先述した通りグループ内の最小値（$gmin$とします）を入れ替えの際に繰り返し使うことでコストを小さくできそうです。
また、提出するものはコストだけなので、実際に並べ替える必要はありません。
グループ内の要素数を $g$ とすると、グループ内での入れ替え総数は $g-1$ 回になります。$gmin$ 以外についてはそれぞれ1回しか動かず、$gmin$については毎回動かすので $g-1$ 回分のコストになります。つまり合計コストは最小値以外の総和+(g-1)*gminであり、少し整理してグループ総和+(g-2)*gminになります。
これをソートが必要な各グループで求めて、それぞれの結果を足し合わせれば答えになりそうです。しかし、これが最小コストとは限らない場合があります。
もう一つの可能性
例えば、
$$ W = [9, 8, 6, 4, 5, 0] $$ $$ A = [0, 4, 5, 6, 8, 9] $$
のような場合（重量は$0$の場合もあります）。グループは2つで $9,0$ と $8,5,6,4$ に分けられます。前述の方法では、前者のコストは$9$で、後者のは$31$となります。しかしここで、後者のグループでの入れ替えで$0$を動かす最小値とした方が、交換回数は2回増えます（全体の最小値をグループ内に引き込む時と取り除く時の分）が、コストが$27$と小さくなります。
つまり、グループ内の最小値より、全体の最小値（ $amin$ とします）を繰り返し使った方がトータルではコストが小さくなる場合があります。その場合のコストは、グループの総和+gmin+(g+1)*aminです。
これで最小コストの見つけ方の見当はつきました。次はどう実装するか考えます。
実装について
コストの計算については2通りとも上で書いたように求められるので、ここでは書きません。
全体の配列からそれぞれのグループを取り出す具体的な方法を考えます。
上の方では $A$ から順に見ていくと説明しましたが、実際は $W$ をforで見ていった方が実装は楽です。 $w_i$ を見てから $a_i$ と同じだったら何もせず、違っていたら $w_i$ のあるべき場所をたどっていきます。そのうち、 $a_k$ が $w_i$ と一致します。一致するまでにたどった $W$ の要素がひとつのグループになります。
あるべき場所をたどるには、 $W$ からその値の位置を見つける必要があります。この処理をfor文で行うと計算量が増大する予感がするのでfor文では行わず、代わりにメモリを使う方法にしました。重量は高々 $10^4+1$ 通りなのでその分の配列を作り、添字に重量である $w$ の値を使い、それに確保する値を $W$ での添字にします。この配列をindexesとします。
これにより、ある重量 $w$ の $W$ での添字はindexes[w]で素早く見つけることができます。また、indexesは-1などを格納することでグループ済みやソート済みのアイテムを区別することもできます。存在しない重量には-1を格納します。
実装ではグループ済みであればソート済みということにしているので、続くfor文で無視するためにグループ済みのindexes[w]には-1を格納しています。
あとはコストの計算をどのタイミングで行うか考えます。グループの総和はグループをたどるときに足していけばよく、グループの最小値もたどる過程でチェックすればよいです。全体の最小値はソート済みである $A_0$ を使えばいいですね。
あとは実装していきます。
コード例
weigh関数での標準出力はデバッグのために残してあります。実際の要素の入れ替えの過程が見たい場合は、コメントアウトしているところを使って見られます。その場合はwhile中の使用済みマークのところの行をコメントアウトする必要があります。
また、少しコメントアウトで補足があります。
折り畳んであります。
// Minimum Cost Sort
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_INDEX = 1e4 + 1;
int weigh(std::vector<int> *W, int n);
int main()
{
// 入力を読み取りweigh関数に渡す
int n;
std::cin >> n;
std::vector<int> W(n);
for (size_t i = 0; i < n; i++)
{
std::cin >> W[i];
}
int weight = weigh(&W, n);
std::cout << weight << std::endl;
}
int weigh(std::vector<int> *W, int n)
{
// indexesは-1で初期化
std::vector<int> indexes(MAX_INDEX, -1);
std::vector<int> A(*W);
std::sort(A.begin(), A.end());
int lowestwv = A[0];
// indexes[weight] = index の形式
for (size_t i = 0; i < n; i++)
{
indexes[(*W)[i]] = i;
}
int weight = 0;
// W[0]からW[n-1]まで順に見る
for (size_t i = 0; i < n; i++)
{
// グループをたどった時に使ったものならコスト加算済みなのでとばす
if (indexes[(*W)[i]] < 0)
continue;
// グループの終わりのチェックのため最初の値を保持
int fwv = (*W)[i];
int av = A[i];
if (fwv == av)
continue;
int minwv = fwv;
int nextIdx = i;
// グループ内最小値を繰り返し動かした場合の合計コスト
int sum1 = 0;
// グループ内の要素数のカウント
int count = 1;
while (true)
{
std::cout << (*W)[nextIdx] << " ";
sum1 += (*W)[nextIdx];
if (minwv > (*W)[nextIdx])
minwv = (*W)[nextIdx];
// 一巡してグループの最初に戻るならwhileを抜ける
if (fwv == av)
break;
count++;
// たどる
nextIdx = indexes[av];
indexes[av] = -1; // 使用済み（グループ済み）マーク
av = A[nextIdx];
}
// 全体の最小値を繰り返し使うときの合計コスト（sum1はまだグループ総和のまま）
int sum2 = sum1 + minwv + (count + 1) * lowestwv;
std::cout << " minwv: " << minwv << " count: " << count << std::endl;
std::cout << sum1 << " " << minwv << " " << count << " " << lowestwv << std::endl;
// 最終的なsum1を算出
sum1 += (count - 2) * minwv;
std::cout << "sum1: " << sum1 << " sum2: " << sum2 << std::endl;
weight += std::min(sum1, sum2);
// こちらを使うなら少し調整が必要
// actual swapping
// while (true)
// {
// int minIdx = indexes[minwv];
// if ((*W)[minIdx] == A[minIdx])
// {
// indexes[(*W)[minIdx]] = -1;
// break;
// }
// int tIdx = indexes[A[minIdx]];
// indexes[minwv] = tIdx;
// indexes[A[minIdx]] = -1; // 使用済みマーク
// std::swap((*W)[minIdx], (*W)[tIdx]);
// }
}
return weight;
}
ポイントとおわり
ポイントとしては、
- ソート済み配列を利用すること、
- 配列の中でグループが作れること、
- 1.グループ内での最小値を動かしていくこと、
- 2.もしくは配列内での最小値をグループ内に一旦持ってきて動かしていくこと、
- この2通りの交換方法からコストの小さい方を選択すること、
- 実際の交換はしなくてもよく、動かす最小値以外は基本的に1度の加算で済むこと、
これらに気をつければいいですね。
今回は難しかった。グループが作れるということに気づいたら結構簡単になりました。indexesは重量の種類が多いと占有メモリが増えるので、多い場合どうすればいいのかと考えました。 $W$ の要素数が高々1000個くらいならforで探してもいいのかなとも思います。
数式表示のためにSimple Mathjaxというワードプレスのプラグインを使っていますが、Markdownで書くと、エスケープのエスケープが必要になって若干記述が冗長になってしまいますね。。波括弧を使う時にA=\\{a_0, a_1\\}というふうにする必要がありました。この時、 $A=\{a_0, a_1\}$ となります。しかもこれだとVSCodeのプレビューでは波括弧は表示されないという。。…慣れるしかなさそうです。
ちょっと調べてみると、グループと呼んでいたものは群論での群というものです。特にこの場合は巡回群と呼ばれるものらしく、あみだくじで表せるようです。巡回置換。大学時代にやった覚えがあるような。記法とか全然覚えてないや。。今度調べます。
以上です。
コメント