問題概要
長さ N の数列が与えられる。下記の操作を任意回行って、コストをできるだけ抑えつつ昇順ソートせよ。
全文はこちら。
解法
以下の 4 つの解法を試して、一番良かったものを採用する。
| アルゴリズム概要 | 有効な X | |
|---|---|---|
| ① | バブルソート | 2.2 ~ |
| ② | 選択ソートっぽいやつ | ~ 0.1 |
| ③ | 選択ソートっぽいやつ改 | 1.8 ~ 2.3 |
| ④ | 隣り合う要素の差の合計を最小化する貪欲 | 0.1 ~ 1.8 |
① バブルソート
X が大きい場合、バブルソートが最適解になる。
最適解になるのは X ≧ 2.71 くらいからのはずだが、他のアルゴリズムがかしこくないせいか X = 2.2 くらいでこれが採用されることもあった。
1 1 1 0 3 0 1 1 2 4 1 1 (1 0) 3 0 1 1 2 4 1 1 0 1 (3 0) 1 1 2 4 1 1 0 1 0 (3 1) 1 2 4 1 1 0 1 0 1 (3 1) 2 4 1 1 0 1 0 1 1 (3 2) 4 1 (1 0) 1 0 1 1 2 3 4 1 0 1 (1 0) 1 1 2 3 4 (1 0) 1 0 1 1 1 2 3 4 0 1 (1 0) 1 1 1 2 3 4 0 (1 0) 1 1 1 1 2 3 4 0 0 1 1 1 1 1 2 3 4
② 選択ソートっぽいやつ
数列内で一番小さい要素を探し、ガバっと先頭に持ってくる。これを N 回繰り返す。
X が極端に小さい場合、選択する範囲の長さに関わらずコストが一律 1 になるので、これで OK。
1 1 1 0 3 0 1 1 2 4 (1 1 1 0) 3 0 1 1 2 4 0 (1 1 1 3 0) 1 1 2 4 0 0 (3 1) 1 1 1 1 2 4 0 0 1 (3 1) 1 1 1 2 4 0 0 1 1 (3 1) 1 1 2 4 0 0 1 1 1 (3 1) 1 2 4 0 0 1 1 1 1 (3 1) 2 4 0 0 1 1 1 1 1 (3 2) 4 0 0 1 1 1 1 1 2 3 4 ...
③ 選択ソートっぽいやつ改
数列内で一番小さい要素を探して先頭に持ってくるのを繰り返すのは②と同じだが、先頭に持ってくる際の処理を工夫する。
具体的には、運ぶ要素をお尻として降順となる最大の範囲を選択し続ける。
1 1 1 0 3 0 1 1 2 4 (1 1 1 0) 3 0 1 1 2 4 0 1 1 1 (3 0) 1 1 2 4 0 (1 1 1 0) 3 1 1 2 4 0 0 1 1 1 (3 1) 1 2 4 0 0 1 1 1 1 (3 1) 2 4 0 0 1 1 1 1 1 (3 2) 4 0 0 1 1 1 1 1 2 3 4
X = 2.0 前後だと、降順になっている範囲を反転することにより最大効率で転倒数を改善できそうな気がした。小さい要素を先頭に運ぶついでに転倒数を改善できたら後で嬉しいよね、きっと。
④ 隣り合う要素の差の合計を最小化する貪欲
6 割のケースをカバーする大本命。0.1 ≦ X ≦ 1.8 でマルチに活躍。
最初は転倒数を最小化する貪欲を書いていたが、どうしても 70 点の壁を超えられず。どこに伸びしろがあるんだろうと悩んだ結果、転倒数を貪欲の評価値として使うのは良くないということに気がついた。
例えば、 1 4 5 6 7 8 9 2 3 という数列は 2 回の反転でソートが完了する。
1 4 5 6 7 8 9 2 3 1 (4 5 6 7 8 9 2) 3 1 2 (9 8 7 6 5 4 3) 1 2 3 4 5 6 7 8 9
ただ、1 回目の反転では数列全体の転倒数が爆増するので、転倒数を減らす貪欲だと選ばれることはないだろう。
要するに、転倒数を見る貪欲は、数列の途中にソート済み区間があるとそれを頑なに守りつつソートしてしまう癖があるのだ。その区間を反転してしまっても後からすぐ戻せるというのに。
そこで転倒数の代替案として思いついたのが「隣り合う要素の差の絶対値の合計」。これならソート済み区間を反転してしまっても評価値へのペナルティにはならず、しかも最小化することが最終的に数列をソートすることにも繋がり、なんかこう、良い感じになりそう。あと計算も転倒数より軽そう。
生の数列でこれを計算すると降順ソートに落ち着く可能性もあるため、番兵として数列の前後に 0 と K（数列の要素の最大値）を挿入した数列で計算してあげます。
0 | 1 1 1 0 3 0 1 1 2 4 | 5 0 | 1 1 1 (0 3) 0 1 1 2 4 | 5 0 | 1 1 1 (3 0 0 1 1) 2 4 | 5 0 | 1 1 1 1 1 0 0 (3 2) 4 | 5 0 |(1 1 1 1 1 0 0) 2 3 4 | 5 0 | 0 0 1 1 1 1 1 2 3 4 | 5
なんとなく良さそうな気はしていたが、実際半分くらいのケースで劇的にスコアが改善され、提出したら 69 点から 83 点まで伸びた。
なんでそんな評価値思いつけるんですか、天才？と思ったが、MM118 を振り返るとかなり典型らしい。というかこのやり取りを覚えていたからこそ思いつけた評価値。人もとい魚は成長するのだ。
連結成分→近傍だけ見て粗い評価、はかなりマラソン典型だと思ってます
— tomerun (@tomerun) May 27, 2020
後はバリエーションとして、隣り合う要素の 2 乗の差とかを使ったりしてみた。
diffMemo1_0[i][j] = abs(pow(i, 1.0) - pow(j, 1.0)); diffMemo1_2[i][j] = abs(pow(i, 1.2) - pow(j, 1.2)); diffMemo1_5[i][j] = abs(pow(i, 1.5) - pow(j, 1.5)); diffMemo2_0[i][j] = abs(pow(i, 2.0) - pow(j, 2.0));
ほんとは「隣り合う要素の差」の 2 乗を使ってみる予定だったのだが実装をミスって↑のようなのを書いて、後からミスに気付くもコレの方がスコアが良かったという。なんでだろう。
あと隣り合う要素の差の合計値で DP を書いてみたが、これはスコアが悪化した。なんでだろう。（この原因はちゃんと考察した方が良かったのでは…？）
最後に、N が小さいケースだと計算が爆速で終わって時間が余っていたので、この④のロジックの評価値に乱数を加えて時間いっぱい回すようにしたら 85.4 点 から 86.1 点くらいに伸びた。さすが乱数先輩頼れる。乱数を加えたら貪欲が伸びるっていうくらい確実じゃってジョセフも言ってた。
おまけ: お蔵入りになった案
関数名として与えられた名前は solveSmart。
基本の方針は先頭から揃えていく。で、例えば今小さい順で 5 番目までの要素が次のような順で数列に埋まっていたとする。（... の部分は任意の数列）
... 5 ... 1 ... 4 ... 2 ... 3 ...
選択ソートだと、こう。
(... 5 ... 1) ... 4 ... 2 ... 3 ... 1 (... 5 ... ... 4 ... 2) ... 3 ... 1 2 (... 4 ... ... 5 ... ... 3) ... 1 2 3 (... ... 5 ... ... 4) ... ... 1 2 3 4 (... ... 5) ... ... ... ... 1 2 3 4 5 ... ... ... ... ... ...
solveSmart だと、こう。
... 5 ... 1 ... 4 ... 2 (... 3) ... ... 5 ... 1 ... 4 (... 2 3) ... ... ... 5 ... 1 (... 4 3 2) ... ... ... ... 5 (... 1 2 3 4) ... ... ... ... (... 5 4 3 2 1) ... ... ... ... ... 1 2 3 4 5 ... ... ... ... ... ...
どうです、smart でしょう。
てな感じで、基本先頭から並べていきつつ、こういうパターンが見つかればそれを smart に処理する。
一見良さげに見えるこのロジックがなぜお蔵入りになったかというと、③や④に完敗したからです。ちゃんちゃん。
