こんにちは
AHC026に参加してきました！
415th / 3136で水パフォ、無事入水することができました
AHC027
課題の確認
問題はcontest page参照
考察
※正しくない部分はあると思います
- 各マスの汚れやすさdは1～1000
- j-k-1は N=20の時-9から17の値を取る、中心が正のあたりにある正規分布
- 毎ターンsum(dij)-d現在地分スコアが増加する
- dが大きいマスに移動距離を増やしてまで寄り道することは基本的にスコアの悪化を招く
- N=40の時は全体で最低でも1600汚れるので、１マスで相殺できない
つまり方針としては、Lをなるべく小さくなるようにしつつ、どうしても訪問済みのマスを通る必要があるときはなるべくdが大きいルートを通る。
でいいとおもってましたが、、、、上位のgifを見る限り違ったようです；；
最終提出
BFSで一番近い未訪問マスへの経路を探す処理をベースに実装しました。
隣接するマスを調べる上下右左の順序を２４通り試したりもしましたが、そもそもLを小さくという方針がよくなかったのか微改善しかできませんでした。
丁寧に経路長とスコアの相関を取ったら相関係数0.915だったので確信してたんですけどね・・・・
AHC入水
AHC024,025,026,027で入水することができました。
各振り返り記事は下記にございます。
感想
AHCをはじめる前までは「焼きなまし法とやらを使わないと戦えないのでは？」と思っていたので、焼きなまし法や山登り法がどういうものなのか座学してからAHC024からヒューリスティクスデビューをしました。
しかし、Contest本番になるとその手法の適用方法がわからず、その場その場においてどうしたほうがスコアがよくなるかというルールを作っていく貪欲なアプローチしかできずすべてのコンテストで貪欲なアプローチで水色までなってしまいました。
余談ですが、アルゴリズムはすでに水色まで取り組んでおり、この貪欲に進める部分で早いソート方法は何だろう？とか、BFSを使おうとかそういったアルゴリズムで学んできた知識は活かすことができたのではないかと思っています。
各コンテストの上位解法のヴィジュアライザを見ると何が起きてるのか全くわからないぐらい上には上があります。
今後の課題としては焼きなまし法や山登り、ビームサーチなどを駆使した最適化コードを実装できるようになるというところだと思います。
引き続き頑張ります！
