AtCoder Heuristic Contest 001に参加しました
参加しました。
初めてRustを書いたのですがめっちゃ怒ってくれるのでありがたいですね。
マラソンに関してはC++教から改宗してRust信者になります。
後作ったコードはここに置いときます。
概要
10000 * 10000の中に点がたくさんある。
各点を丁度1個含む長方形を点の数だけいい感じに作る。
各点にはこれくらいの面積が欲しいという指標があってその指標に近ければ近いほど点が高い。
結果
最終提出で伸びてた！
— 𝐓𝐓 (@TT_beginner) 2021年3月14日
目標の46Gまでいけたっぽい！
後はシステスお祈り pic.twitter.com/OYKAFjv8ml
#AHC001
— 𝐓𝐓 (@TT_beginner) 2021年3月14日
まじめにやった&Rust初めて触った長期マラソンでした
・初期解で1*1を作ってから-25~25のランダムで伸び縮みする焼きなましを書いた(昨日まで)
・最後に点数が低そうな四角形を雑に伸ばせばスコア伸びるのでは!?で雑にやった
46,227,785,092点 pic.twitter.com/NiebYLXYT4
46G届いたやったね！
各提出ごとのメモ垂れ流し
初回提出
方針: 愚直に長方形を置くだけ
in: 76,402,184
judge: 1,466,059,961
place: 444
2回目提出
方針: 愚直に長方形を置くだけ+psが取れるなら確実にとる
in: 初回の10倍くらい(取り忘れ)
judge: TLE
place: ---
3回目提出
方針: 初期解をpsを囲む1*1の四角に変更(初期解生成を高速化), 四角を広げる/縮めるで得点を伸ばす方針に 愚直更新なので局所解で死ぬ
in: 608,209,485
judge: RE(なんで～～～～～～～)
place: ---
4回目提出
方針: index-out-of-rangeのバグを直した:angry_face:
in: 817,702,176
judge: RE(うるせ～～～～～～～～～しらね～～～～～～～)
place: ---
5回目提出
方針: index-out-of-rangeのバグを直した, やきなましをしようとした(うまく収束せず-1量産で一旦諦め)
in: 503,326,678
judge: RE(うるせ～～～～～～～～～しらね～～～～～～～)
place: ---
6回目提出
方針: run.shでin内全部回してバグを見つける。random generator嫌いになりそう
in: 613,761,431
judge: 30,512,002,092
place: 344
7回目提出
方針: pointの更新を1点にして高速化、焼きなまし(嘘)の遷移を消して山登りに
in: 654,662,382
judge: 30,512,002,092
place: 344
8回目提出
方針: 更新時の得点計算を高速化
in: 忘れ
judge: 37,853,983,860
place: 401
9回目提出
方針: 全く触られていなかった点に対して0.1秒かけてランダムを回し続けた。ダメ。
in: 702225411
judge: 37,266,198,805
place: 472
10回目提出
方針: 焼きなましをそれっぽくした&面積をいい感じにすべく縦を揃えたら横は面積以下になるようにして よしなにする
in: 773~778くらい
judge: 42,862,187,666
place: 401(順位が変わってない...:cry:)
10回目提出
方針: 四角を伸び縮みする方針に変更
in: 847,720,305
judge: 44,936,295,721
place: 354(点数はめっちゃ伸びたのに順位が伸びない...全人類強すぎる)
10回目提出
方針: 伸び縮みする幅を-10 ~ 10に変更
in: 847,720,305
judge: 45,014,611,474
place: 391(400点台を回避できてｳﾚｼｲ...)
11回目提出
方針: 伸び縮みする幅を-25 ~ 25に変更, TLを4.75secに拡張(頑張れ)
in: 905,998,522
judge: 45,653,976,336
place: 304
13回目提出
方針: 温度関数をいじった
in: 920,053,357
judge: 45,936,069,295
place: 305(46G乗らね~~~~~)
ここらへんでジャッジのコンパイルオプションと手元実行のオプションが違うことに気付き、直す。ローカルでの点数が合う。
最終提出
(サボりまくってたら最終日!?あたしどうなっちゃうの～～～)
方針: 雑に点数が低いやつを伸ばした
in: 945くらい
judge: 46,227,785,092
place: 490(人類強すぎ)
学び
上位の人を見ると焼きなましじゃなくて山登りで貪欲にやっててビビった。
クソデカ広告をいっぱいに広げてから削る方針もあってほえ～となった。
今回の自分の立ち回りで気付くべきは四角を伸ばしたら接触"した"方の四角を削るといい感じになるということだった。
後結果だけをビジュアライズするやつしか配られないときは自分で自作するのは結構いい方針ということも学んだ(急がば回れの精神)。
完走した感想
長期間コンテストは生活習慣崩壊するので注意！(6時寝常習犯)
後めっちゃ楽しかったけどまだ下手なので手詰まり感がすごいけど頑張って成長したいね
おまけ
マラソン、Rustしか勝たんのでこれからもRustで触っていきます
— 𝐓𝐓 (@TT_beginner) 2021年3月14日
(floatのcompareだけ許してほしい...)
