0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴6年目のかえでです。
これは、2025年4月26日土曜日19時から23時までの4時間で開催された「BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046）」の復習記事です。
本番では、986人中426位という結果に終わりました。ちゃんとしたプログラムが書けずに終わってしまったので、もう一度落ち着いてゆっくりと解きたいと思います。
1.問題の概要
2.コードを書きなおす
今日は2025年5月17日です。
すぐに復習しようと思っていたものの、すぐにゴールデンウィークに入ってしまったこともあり、全く復習が進みませんでした。その後もMM161をやっていたり、ABCの復習をしていたりして、気がつけば明日が次のAHCの開催日となっていました。
今日は比較的時間があるので、少しでもやり直したいと思います。
3.貪欲
- 今の位置から次の目的地までを１セットと考えます。
- 今の位置の「上下左右のいずれかにブロックを置く」、もしくは「ブロックを置かない」を全て試します。
- その後にかかるターンをシミュレーションして一番スコアが良かったものを採用します。
コードを書きます。100テストケースの平均は1441になりました。
提出すると、216230点になりました。本番141位相当のスコアです。
4.焼きなまし
3の貪欲解を初期解として、ブロックの配置を焼きなましで改善します。
- ブロックの削除や追加を次の目的地に向かう前の現在位置で行います。
- 評価はブロック配置変更後のターン以降をシミュレーションします。
- 焼きなまし時間は1.9秒行います。
100テストケースの平均は1447になりました。
提出すると、TLEしました。
実行時間を1.7秒にして再提出をします。得点は217267点になりました。本番85位相当のスコアになりました。
この後、使わないブロックがあれば取り除く、複数のブロックを一度に変更する等を行ってみましたが、スコアはよくなりませんでした。
5.まとめ
seed0のターン数です。
- 滑走は使うが何も置かないとき・・・494ターン
- ブロックの配置を最初から全パターン試す貪欲・・・207ターン
- ブロック配置を焼きなます・・・198ターン
4時間でここまでできればなあと思いました。
解説にあげられているブログも一つずつ読みました。解法ブログがあるととても参考になります。
自分も短期のときにも記録をしてブログを書くようにしたいと思いました。
さあ、明日のAHC047をがんばりたいと思います！
