AtCoder Heuristic Contest 003

問題

https://atcoder.jp/contests/ahc003/tasks/ahc003_a

結果

(システムテスト待ち)

日記

1 日目

勾配: https://www.wolframalpha.com/input/?i=plot+0.998%5E%281000+-+k%29+for+1+%3C%3D+k+%3C%3D+1000

interactive だからツールの改修に手間がかかるね。とりあえず GitHub 上で 2000 ケース走るようにしたけど、なんだか動いてない。

上位勢が 93e9 出しててわからん。適当に Dijkstra とかしたら 63e9 くらいだが？ $2312311 \sum 0.998^{1000 - k} \approx 10^9$ なので 100 ケースあると理論値は 100e9 になる。 70 回使って調査して残りは厳密最短だと 93e9 になる。

直線の移動が多いと関連する行や列が減って考えやすそう。常に直線 3 本で移動できるわけだけど、必ずそうするというのはどうか。ほとんどの部分を直線 2 本で移動し、残りは適当にするのはどうか。

scan するのでなくてへびのように埋めるのはどうだろうか。 $\log 30^2 \lt 7$ なので、グリッドのそれぞれの行や列を確率 1/2 で使うようなクエリを 7 回聞けばあとは厳密最短になる

M = 2 の場合があること気づいてなかった。誤読してた。 M = 2 の場合を直したら点数が跳ねた。 M = 1 の場合の点数も同様に跳ねてるのはなぜ？バグが直った？ともあれよかった。 95e9 で暫定 1 位になった。この感じだと最終日は 98e9 くらいまで出そう。

2 日目

精度勝負なので 2000 ケースチェックは必須に見える。 GitHub Actions が動いてない問題をなんとかしていきたい。なんとかした。

焼きなまし https://github.com/kmyk/atcoder-heuristic-contest-003/commit/d68fc7d25f818aea3b6e25f284bce606883bc3fd 95608505033 点

M = 1 のときの予測器と M = 2 のときの予測器を作ってミックスした。なんだこれ。Kaggle かな？

線形計画問題にして最適解を出せないか？ AtCoder には GLPK 入ってないぽい

やっぱりヘビするやつだめ？初手で M の値の判別だけでもできないか？

結果に 0.9 から 1.1 が掛けられたものが帰ってくるけど、この係数も含めて予測してはどうかこれが常に 1 だったら性能上がるのか試しておきたい

そろそろ M や D の値ごとに分類して改善可能箇所を探すべき。たぶん生成器やテスターを再実装した方がいい

もしかして、普通に全部をそっくりそのまま予測しちゃうのできるのては？初日にだめだったのは M = 2 のまわりのなにかぽいし、もう一度やればできるかも

M = 2 のときの切り替わり点の予測ってほんとにちゃんとできてるの？端から端へ線型に変化すると緩和したりとかの方が良かったりしない？

辺数が 1800 くらいあって得られる緩い等式が 1000 なので完全予測はかなり無理がある

計測環境を完璧にした。 M = 2 や D が大きいときほど点数が下がるのは分かるけど、D が 100 あたりでも下がってるのはなんで？

M	D	score
1	100	96624308340
1	300	97245317080
1	600	97595283356
1	900	97314338004
1	1200	97040371826
1	1500	96590920656
1	1800	96031089794
1	2000	95493223736
2	100	93443549210
2	300	94399588852
2	600	94951593110
2	900	94906088996
2	1200	94686509764
2	1500	94271982974
2	1800	93637385840
2	2000	93183994104

(https://github.com/kmyk/atcoder-heuristic-contest-003/commit/cf34ccc4915366a5d242e4bfffe84003025191d8)

ヘビをしたけどだめ。なんで？

仕切りをすこしずつ動かした方が得点がいい。なんで？どこかにバグがありそう。

D = 0 を試すとよい気がしてきた。あと e が常に 1 とかも。さすがに M = 1 かつ D = 0 かつ e が常に 1 なら 99e9 が出る。

0.6e9 はわりと大きいらしい？たとえば 99.3e9 が 98.7e9 になる。 95.8e9 から 97.1e9 に上げようとしてるのでこれは大きい。

絶対にヘビは正しいと思うんだよね。 M = 2 のときだけやるとかはどうか？

採択確率をいじってみても改善してくれない。まあわかる。

最適な近傍へ直接ジャンプするやつやってないよねそういえば。やりましょう。やったけどだめだった。なんで？確率で悪くなる動きがないから局所最適になってるのかな？普通の近傍と混ぜるのを後で試しましょう。

100 ケースしかないと 95.5e9 から 96.1e9 くらいの範囲で点数がぶれる。しかも実行時乱数に依存してぶれるのでなく seed に依存してぶれる。おそらく M = 1 と M = 2 の比とかだと思う。あまり順位表を気にしすぎず dashboard を見て考えた方がよさそう。

M	D	score
1	100	98698726544
1	300	98640402720
1	600	98340810884
1	900	97895237522
1	1200	97164572912
1	1500	96404054744
1	1800	95292891690
1	2000	94355834356
2	100	96038742946
2	300	95881495486
2	600	95884085018
2	900	95403838512
2	1200	94893684446
2	1500	93856283974
2	1800	93221743440
2	2000	92547695850

(https://github.com/kmyk/atcoder-heuristic-contest-003/commit/0a6b2d9309ecdb8371bd9f843bc76168f1df454cv)

仕切りをすこしずつ動かすやつの完全な計測をまだしてなかったからしたけど、単純に良くなっているわけではなかったぽい。どういうこと？やっぱりごちゃまぜ 50 ケース平均だけを見て判断するのかなりよくないらしい。

最初から各行各列の平均値が分かっていてかつ更新なしの場合にどれくらいの点数になるか確認するべき。

初手は対角線を通るように N の形に動くことにすると対角線部分は均せて 2 変数間の等式が取れそう。 30 * 2 やれば予測できないか？いや、カクカクと動いて 3 変数間の等式を得ても同じことだから無駄だな。

M = 2 の場合に区切りの位置をどうやって見つけるかを考えた方がよさそう。なお、そもそも不可能という可能性もあって、その場合はよい近似を考えることになる。

計算量を落とすみたいな方向も考えていきたい。スコアを 100 で割ったものについてまず焼いて、その後により詳しく焼くというのはどうか。

3 日目

最初から各行各列の平均値が分かっていてかつ更新なしの場合の点数を確認した。なんだかぜんぜん何も言えない感じになった。

M	D	avg opt
1	100	999607414
1	300	998454403
1	600	995893464
1	900	991466965
1	1200	984540029
1	1500	979478955
1	1800	966771905
1	2000	955727963
2	100	999984964
2	300	998732445
2	600	995492518
2	900	992376619
2	1200	982493982
2	1500	971381434
2	1800	957025495
2	2000	946862778

ついでに各時刻での点数も表にしておく。

$k$	$0.998^{1000 - k - 1}$	$2312311 \cdot 0.998^{1000 - k - 1}$
0	0.1353	312937
100	0.1653	382298
200	0.2020	467034
300	0.2467	570551
400	0.3014	697012
500	0.3682	851503
600	0.4499	1040236
700	0.5496	1270802
800	0.6714	1552472
900	0.8202	1896574
1000	1.0020	2316944

現在の 1 位は 972000000 くらい。現在の私は 959000000 くらいなので後 13000000 くらい上げる必要がある。この点差は k = 1000 のクエリ 5.6 個分かつ k = 1 のクエリ 40 個分である。できるの？できそうな気もするけど無理でしょという気もする。きびしい。

やっぱりへび系で M = 1 を 0.999 するやつをという気分になるが、さっきの表を見ると D = 2000 で 0.956 なので可能性はないことが分かる。

時間を 20 倍にして実行しておく。以下のようになった。むしろ悪化してないか？なぜ？ M = 1 のみで悪化して M = 2 では改善してるように見えるので、M = 1 / M = 2 の判別に悪影響が出たのだろうか。

M	D	score
1	100	98482768964
1	300	98454844218
1	600	97948625832
1	900	97446953238
1	1200	96665868138
1	1500	95732349762
1	1800	94678237786
1	2000	93903894844
2	100	96373420082
2	300	96103825606
2	600	96124673460
2	900	95656554932
2	1200	94901546636
2	1500	94319302104
2	1800	93571151702
2	2000	92843782122

7 日目

97e9 は出さないといけない状態になってる。やっぱりか。でもさすがに 26 位はつらい。 M ごとや D ごとの改善をやる環境を作った人が 10 人もいるとは思えないから、落ち付いてやれば勝てるはずなので、やっていきましょう。

クラウドしようとしたけどうまくいかなかった。最初は GCP n2d-standard-96 を借りようとしたのだけど quota で弾かれてしまったので申請受理待ちでもある。 96 vCPUs で preemptive なら $0.9/hour とコスパが良い。しかたがないので AWS c5.12xlarge を借りようとしたが、こちらもリクエストがうまくいかない。なお 46 vCPUs で spot instances で $0.6/hour である。

M = 1 の予測器しか使わないようにしても点数がほとんど変わらない。なんで？ M = 2 のがずっと壊れてたりした？

コンパイルし忘れてただけだった……

なんか微妙にバグってたらしくて、しかも修正したら点数が下がった。どうして……

1 位は 97.4e9 なんだけど、私は M = 1 に限っても 97.1e9 なので、なにかがおかしい。なんでしょう？ M = 2 だと点数が悪化するのは明らかで、そのことを踏まえると 1 位は M = 1 で 98e9 は出していないとおかしい。

やはりヘビ系を丁寧にもう一度試すしかないのではないか。

M	D	score
1	random	97053876412
2	random	94274015595
1	100	98577578214
1	300	98501531496
1	600	98148661124
1	900	97698874374
1	1200	97034888958
1	1500	96188761210
1	1800	95111907576
1	2000	94134142668
2	100	95013886388
2	300	94821249206
2	600	95259408896
2	900	94862436404
2	1200	94359972412
2	1500	93978544788
2	1800	93143672192
2	2000	92566081600

(https://github.com/kmyk/atcoder-heuristic-contest-003/commit/8e01eb494fe2aa2ea684c3b39eb75f6059d1e83e) (提出)

8 日目

冷静に考えると、へびをしようとも得られる等式の数は変わらないので無駄です。だめじゃん。

M = 2 の sep をなくして線形に変化させるようにした。うまくいってない。ところで D = 100 で点数が下がってるのなんで？

M	D	score
1	random	97062585172
2	random	93710623867
1	100	98445557550
1	300	98141191654
1	600	98067178080
1	900	97533181634
1	1200	96793983770
1	1500	96222675420
1	1800	95199094660
1	2000	94330168762
2	100	93437991552
2	300	93787882096
2	600	94388824796
2	900	94522921898
2	1200	94164668816
2	1500	94023241658
2	1800	92969269832
2	2000	92326946776

パラメタ調整してたらちょっと伸びた。

M	D	score
1	random	97400970593
2	random	95124207627
1	100	98774356766
1	300	98733582698
1	600	98481082308
1	900	98029819104
1	1200	97336080922
1	1500	96640105008
1	1800	95485667630
1	2000	94609499264
2	100	96334142918
2	300	96268115142
2	1200	95102778480
2	600	96045895750
2	900	95595061846
2	1500	94512638768
2	1800	93433635818
2	2000	92797861194

(https://github.com/kmyk/atcoder-heuristic-contest-003/commit/f3d412a0de385e0d1d80f96c411a7d4976584d8d)

9 日目

c5.24xlarge でパラメタの微調整のみ

M	D	score
random	random	96319490239
1	random	97333367775
2	random	95191013733
1	100	98714000480
2	100	95992663802
1	300	98759505542
2	300	96365969616
1	600	98446319932
2	600	96192563330
1	900	98045700544
2	900	95779246582
1	1200	97309277280
2	1200	95243462318
1	1500	96567481926
2	1500	94574616574
1	1800	95515239230
2	1800	93712137794
1	2000	94646338608
2	2000	92891820126

(https://github.com/kmyk/atcoder-heuristic-contest-003/commit/421323ea6b5447b86ff29a79b9ee8568ba962a77) (最終提出)

kmyk / atcoder-heuristic-contest-003 Goto Github PK