問 ALDS1_6_D
Sort II - Minimum Cost Sort
の解法。
問題原文はこちら。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
独自解法。
配列の要素をマスとし、ソート後にあるマスに入る数字をそのマスの正しい数字と定義します。
問題の着目点。
要求されるタスクは、4,1,3,5
とあったとき
1を正しいマスに確定する。
3を正しいマスに確定する
4を正しいマスに確定する
5を正しいマスに確定する
ということです。
これを踏まえて解法を考えます。
解法は以下の通り。
処理Ａ
数字列が与えられたとき、一番小さな数字に注目します。
一番小さな数字の入ってるマスに入る正しい数字。
これと一番小さな数を交換します。
一番小さな数が自分の正しいマスに入るまでこの作業を繰り返します。
正しいマスに入れば処理は終了です。
次は２番目に小さな数３番目に小さな数、、、も同様に処理Ａを繰り返します。
これは、一番小さな数と、その小さな数のあるマスを正しい数で交換すれば、正しい数は最も低いコストでマスを確定できるのでこの処理は妥当です。
しかしこれだけでは処理はうまくいきません。
２番目に小さな数以降を処理する場合。
その数をｍ番目に小さな数だとします。
処理Ｂ
まず処理Ａをした場合を考え、この時の交換手順をＲとして記録します。
処理Ｃ
次にｍ番目に小さな数と一番小さな数を入れ替えてその後はＲの交換手順通りに交換し、入れ替え終了後ｍ番目に小さな数と一番小さな数を交換した場合。
Ｃのほうがコストが小さくなる場合があります。
Ｂ，Ｃを検討し、小さいほうを処理Ａのコストとして確定します。
しかしＲという点ではＢもＣも同じ処理ですから、処理Ｂの副産物として簡単に処理Ｃの場合のコストが出ます。
後は上記処理を効率的に実装した結果。
私の場合この問題の最悪の計算量はＢｉｇＯ 1000*log(1000)という結果となりました。
ＡＯＪを知っている方ならコードが合格したらまず解法に間違いがないとご理解いただけると思います。
私は６時間ほどコードをいじくりながらああでもないこうでもないと一人考えました。
その結果上記解法を思いつきこれに従いコードを実装したところ合格したので。
まず解法に間違いはないと思います。
解法者
兵庫県加古川市加古川町南備後79-16
堀江伸一
0 件のコメント:
コメントを投稿