Topcoder Marathon Match 97
作成日：2018.02.01
カテゴリー：競プロ 参戦記録
目次
- 1日目(2018.01.25)
- 2日目(2018.01.26)
- 3日目(2018.01.27)
- 4日目(2018.01.28)
- 5日目(2018.01.29)
- 6日目(2018.01.30)
- 7日目(2018.01.31)
- 結果
- 振り返り
1日目(2018.01.25)
問題文を読む。焼きなましっぽいので、まずはそれを実装することにする。
ただ小さいケースで最適解が計算で出せる可能性もあることを心に留めておく。
点対間の距離を求めるのにsin関数が必要だが、これを何度も呼び出すと重い。
だからこれは初めに計算してメモしておくことにする。
一番簡単な2点swapを遷移とする焼きなましを実装する。
提出すると、$854615.38$点の$3$位になる。
まだ始まったばかりなので順位にそれほど意味はない。
また今回はスコアが相対評価であるから、提出前にどのくらい順位が上がるかが読めない。
スコア変動に関係する点を点対ごとに列挙しておくことによって行う高速化を思いつく。
まだ序盤であるから高速化をするのは後で良いとも思ったが、そこそこ効果があると思ったので行うことにする。
実際に実装して確かめてみると、遷移回数(正確にはある点対をswapするかどうかを決める回数)が2,3倍ほどになる。
素点も劇的に伸びたケースが結構ある。
提出すると$922647.06$点の$2$位となる。
2日目(2018.01.26)
スコアを整数にするということや、答えを32bitではなく8bitで保持するということという高速化の手段ばかりが思いつく。
どちらもそれほど変えるのに手間がかからないので、実行してみる。
しかし遷移回数が増えなかったり、逆に減ったりしたので元に戻す。
どの点対が遷移で使われているかを見てみることにする。
すると特に終盤では近い点同士でのみ遷移が起こっていることを発見する。
そこで時間の経過とともに近い点同士だけを見るようにすることで、有効そうな遷移だけを扱うことにする。
実行してみると半数以上がわずかに改善するものの、一部ケースで大幅に悪化するという結果になる。
少しパラメータをいじってから提出すると、$846100.00$点の$9$位から$876600.00$点の$6$位になる。
高速化が上手くいかなかったのが納得がいかないのでもう一度試してみる。
するとスコアを整数にする方は遷移回数が$5%$ほど増加する。
一方、答えをint型からuint8_t型に変更する方は遷移回数が減少する。
調べてみるとuint_fast8_t型というものがあるとのこと。
これで試してみると若干の増加となる。
スコアは増加したものと減少したものが同じぐらいであるようだ。
提出すると$852358.49$点の$7$位から$822830.19$点の$9$位となる。
3日目(2018.01.27)
前日の最後の提出で点数が下がったのが納得がいかない。
そこでTopcoderのテスト機能でエラー出力が見れることを利用して遷移回数を調べてみる。
するとケースによらずほぼ遷移回数が同じであることを見つける。
$N$が大きいほど遷移回数が減るはずなので、これはおかしい。
Topcoderでは時間取得が遅いと言われているので、ここが律速になっていると推測される。
そこで今まで使っていたgettimeofday関数を、Topcoder上でも遅くならないと言われているrdtscを用いた方法に変更する。
すると遷移回数がTopcoder上でも手元での値と比例する結果になる。
提出すると$832045.45$点の$10$位から$884015.15$点の$2$位となる。
これまで高速化をしてきたが、これがどの程度効果を上げているのか確かめるために実行時間を短くしてみる。
すると$1/4$に減らしてもスコアが大きくは悪化しないことが分かる。
その一方で実行ごとにスコアが大きく変動するケースがあることも発見する。
そこで1回当たりの実行時間を減らす代わりに焼きなましを何度か行うことにする。
いろいろ試したところ、実行時間を$1/3$にして3回の焼きなましを行うのが良さそうであることが分かる。
Topcoderのテストにおいて1ケースだけTLEが出たが無視してそのまま提出すると、$881250.00$点の$3$位から$662794.12$点の$28$位となる。
下位の点数の変化から分析すると$100$ケース中$28$ケースでTLEになっているようだ。
もしTLEになっているケースでもTLEになっていないケースと同じ割合の得点を得られるとすると、$920k$点を超えることになる。
2時間の提出制限の後に実行時間をほんの少し短くしたものを提出すると、$905661.76$点の$1$位となる。
下位の点数の変化によると、今度はTLEになっていないようだ。
4日目(2018.01.28)
Topcoder上では手元の約$3$倍で動くから、焼きなましを繰り返す回数を$3$倍にしても良いのではと思う。
動作確認として手元で動かすと、実は前のものとスコアがそれほど変わらないことが分かる。
そこで何回の焼きなましをするのが良いかをもっと広い範囲で探してみることにする。
すると手元で$500$から$1000$ぐらいにするのが良さそうだと分かる。
$Topcoder$のテストでもいくつか試すと$2000$ぐらいが良さそうである。
とりあえず提出すると$904210.53$点から$911644.74$点(順位は$2$位で変わらず)となる。
ただ他の人のスコアは上がったり下がったりしているので、素点が一様に良くなったわけではない。
3点swapや焼きなましの温度変化、繰り返しの回数の変更を試してみたがなかなか良くならない。
それでも手元で少し良くなったものを提出するも、$910259.74$点の$2$位から$897402.60$点の$3$位となる。
他の人で点数が下がった人はいないようなので、有効ではなかったようだ。
スコアの更新しているタイミングを調べてみると、初めの方に固まっていることに気付く。
焼きなましの時間を短くして何度も繰り返すと良くなったのは、より多くの局所解を訪れることができたからであろう。
それならば一度解を出してから焼きなましを繰り返した方が良いだろう。
そこで初めに$2$秒ほどの焼きなましで解を出し、その後短時間の焼きなましを繰り返すことにする。
これを提出すると$893571.43$点の$3$位から$906623.38$点の$2$位となる。
5日目(2018.01.29)
焼きなましの後に山登りする処理を書き加えたものを提出する。
$887083.33$点から$890654.76$点(順位は$6$位で変わらず)となる。
6日目(2018.01.30)
色々いじっていると、焼きなましを繰り返す回数を$15$回にした方が良いことが分かる。
提出すると$888924.73$点から$900645.16$点(順位は$7$位で変わらず)となる。
7日目(2018.01.31)
パラメータを色々変えてみるも、より良い解を得ることができない。
そのまま時間切れ。
結果
システムテスト前は$879636.36$点で$9$位。
解法は遷移が2点swapだけの焼きなまし+山登りで、$2.5$秒行った後さらに$15$回行う。
焼きなましの温度変化は線形である。
2点swapは、初めの$3/4$の時間では$1 + N/16$以下の距離(円弧上で隣り合うものの距離を$1$とする)にある点対のみを見て、残り$1/4$では徐々にその距離を小さくしていく。
振り返り
実行するたびにスコアが大きく変わるのは、焼きなましが上手くできていないということなのだろうか。
温度変化を工夫すれば良いのだろうか。
とりあえず焼きなましをするのは簡単であるが、それを詰めるとなると難しい。
＜(古い記事)
関連
Topcoder Marathon Match 97 最終結果 (新しい記事)＞