kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_6_D: Minimum Cost Sort

ALDS1_5_Dが思考★★★、実装★★☆だったのに対し、今度は思考★★★★☆、実装★★☆
思考の星が1個半多い
これはダメかもしれんね

荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた
コストがかかり、トータルのコストが最小になるようにソートするというもの

  • コストは交換する要素間の距離には依存しないので、離れた要素を入れ替えたほうがお得
  • 素数は1000までなのでオーダはそんなに気にしなくてもいいのかもしれない
  • 最小値しかもとめられてないので、もしかすると実際のソートの手順は必須ではない

思いつくのはそれくらい
必須ではないと言っても、実際には手順まで求めないとダメな気もする

クイックソートにしてもマージソートにしても、どれを交換するかは
アルゴリズム任せになっているので、交換する要素をどれにするかって
いうのを決めるのは未知の世界

こういう入れ替え方でソートできますけど、こういう入れ替え方でも
できますよ、っていうのはどう考えるのか
普通にソートしてみてからその結果に持っていけるように交換順序を考える、
でいいのかな
そうやったとしてもこれが最小です、って言うのはちょっと難しそうな
オーダあんまり気にしなくても、と言ったって総当たりってわけには
行かないだろうし

紙とペンでやってみた限り、重いものから順に正しい位置へ
入れていくようにするのがいい結果に繋がりそうだ
二つの荷物を入れ替えると両方ちょうどいい場所に来るっていう
ケースは優先的に入れ替えたほうがいいのかな
最初からそうなってれば放置しててもそうなるけど、入れ替えてる
途中でたまたまそういう配置になるっていうこともありそうな

コスト最小が回数最小であるとも限らないし
極端な話、入れ替えてどちらも正しい位置にこないような移動が
最適じゃないとも言い切れない

さてどうしたものか