pretest29位。最終27位。
ツイートをまとめておきます。
第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） pretestは29位でした。今のところAHCでの最高順位! システムテストで下がらないことを祈る！
・序盤はあまりやる気が起きませんでした。今週はWTFもあるのでほどほどに……という気持ちでやっていました。
・入口を根とするBFS木を作って、葉から埋める方針を考えていました。葉の方から順に埋めると、その先祖のノードでは何を置いて良いかを判定できるので。Sが小さく、D-Sが大きいものから埋める貪欲で30～31点
・それを、なんとなくDが大きい順にソートし直したら点数が31から39まで跳ね上がってびっくり。突然やる気が湧きました。これを山登りとかで改善すれば40はいきそう、と。
・WTF open一日目で青に落ちて二日目はAHCにあてることを決意。山登りするための高速化と、遷移を書いていました。
・遷移としては、「既においた作物を別の似た作物へ変える」「BFS木の親を別のものへ付け替える」の二つを実装。先祖のノードで使うことにしていた作物は一旦全部削除しなくてはいけない……といったあたりが分からず実装に苦戦。実装できたら40に乗りました。
・実行時間が伸びればそれなりに点数が伸びそう、と最終日にRUSTへ書き換え。Chat-GPTや自分の以前のRUSTの提出を見ながら実装して41まで伸びました。
・さらに、PyPyで試したときはあまり効果がなさそうだったけどRUSTなら、と焼きなましを試してみたら416まで伸びました。今まで、山登り→焼きなましではっきり点数が伸びた経験がなかったのでびっくり。嬉しかった！
・あとは温度調整などをして終了。
0 件のコメント:
コメントを投稿