yukicoder という有志作成の問題を解くコンテストに参加した。 今回は4時間の短時間 heuristic コンテストで、作問は E869120 さん。
問題
https://yukicoder.me/problems/no/5020
N (=45) 枚のカードの表裏に数字が書かれている。
2 枚のカードを選ぶと、表裏の数字のそれぞれを 2枚の平均に変化させる。
50 回以内の操作で 0 枚目のカードの表裏の値の両方をできるだけ 5 x 10^17 に近づけたい。
結果
39,532,303 点で 27 / 84 位とまずまず
解法
適当な貪欲法 (スコアが高くなるように 0 と何回か交換) で初期解をつくり、ランダムな操作の挿入/削除を近傍とした焼きなましを行った。 改善としては初期解の改善や、近傍の変更として
- 操作内容のランダムな変更
- 適当な 2 操作の順番の swap
を行ってみたが、スコアは改善せず。
終了後
writer 解を見てみると、0 と他すべてのカードの交換を基本として操作順の swap を行って焼きなますというものだった。 これだけで 80M 以上出るとのこと。
自分の解と比べて何が良いのかというと、近傍でのスコア変化が小さく設計されているということらしい。 最初のほうの順番の変更はその後の操作で値が均されてほんの少ししかスコアが変わらなくなるということだろう。
実際少しためしてみると、ほとんどチューニングしなくても 78M のスコアが出た。 焼きなましの改善で何をすれば良いかわからなくて止まってしまったけれど、今回のポイントはスコアが極端に変化しないように近傍を設計することだったのかなあと学びを得た。
