- 0.はじめまして
- 1.問題の概要
- 2.コンテスト時の振り返り1（本番491位相当）
- 3.コンテスト時の振り返り2（本番472位相当）
- 4.コンテスト時の振り返り3（本番399位相当）
- 5.コンテスト時の振り返り4（本番291位相当）
- 6.コンテスト時の振り返り5（本番172位で終了）
- 7.復習貪欲ペア解法
- 8.復習ペア解法乱択
- 9.復習ビームサーチ
0.はじめまして
はじめまして、もしくはお久しぶりです。競技プログラミング歴7年目のかえでです。
これは、2026年8月29日土曜日午後3時から午後7時まで開催された、4時間短期コンテスト「第13回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 070）」の復習記録です。
参加時はスコア485,984,930、パフォーマンスは1662、506人中172位という結果でした。
1.問題の概要
- N×Nマスのエリア（N=100固定）に10000回怪異が起こる
- M個（M=3固定）の位置関係を定め、各ターンでそのうちのどれかを使用して今いる位置から移動する
- 移動した場所にお札を立てることができる
- 各ターンで怪異が起こる際、お札との距離が近い方が良い
- 盤面は移動時には上下左右がつながっているが、怪異とお札の距離はつながっていないものとして、マンハッタン距離で計算する
- 10000ターンの間、全ての場所で怪異が起こるので、怪異が起きた場所とお札の距離が小さくなるよう、お札を立てながら移動する
2.コンテスト時の振り返り1（本番491位相当）
- 問題を読んでもどうすればよいのかよくわからなかったので、3方向の指定を(0,0)、(0,1)、(0,2)として、各ターンの行動は乱択をしました。
コンテスト開始時から約18分後に実装を終えて提出をすると、4,545,045点を得ました。これは本番491位相当の得点です。
ビジュアライザを見ると、一番上にしかお札を置けていませんでした…。
3.コンテスト時の振り返り2（本番472位相当）
ビジュアライザのアウトプットに3方向の座標を適当に入れて変化を見ました。
- (20,20)、(50,50)、(0,80)
スコアが上がっている！seed0のスコアは30355から208264に上がっていました。
提出をすると31,278,014点を得ました。コンテスト開始から27分が経過していました。
4.コンテスト時の振り返り3（本番399位相当）
ああ、そうか。満遍なくお札を置ければ、どこに怪異が起きても距離は一定以内におさめることができるのか、と思いました。
できるだけ重ならずに置ける座標をビジュアライザを見ながら手で試します。
- (2,5)、(5,1)、(0,10)
提出すると、302,154,304点になりました。コンテスト開始から約32分が経過していました。
5.コンテスト時の振り返り4（本番291位相当）
ここからどうすればよいのかわからず悩みました。良い座標の組み合わせを調べたいと思いましたが、全探索するにも時間がかかるし、どのような条件にすればよいのかもわかりません。なんとなく100と互いに素になる数を使った方が少しずつ位置がずれて良さそうに思います。素数が良いのかなとも思いました。
- (16,5)、(5,17)、(0,5)
これまで行動は乱択にしていましたが、同じ行動を続けると、100回でループすることに気がつきました。同じ場所になったら別の行動を入れて少しずらすことを行いました。
そうか、これまでのプログラムは重複が多いんだ。
プログラムを重複を避けるように修正すると、ローカルの100テストケースの平均はぐっと上がりました。
提出をすると、416,921,469点を得ました。前回より3割ほどスコアがアップしました。
しかし、時刻は午後6時12分。コンテスト開始から3時間以上経過し、残りは一時間も残っていません。
ここまできてやっと下のグラフが最後の方でなだらかな山になっているのを見ることができました。
6.コンテスト時の振り返り5（本番172位で終了）
最終的には、同じ位置をなるべく重複して訪れないように行動を選択した初期解を作り、それをもとに、移動ベクトルを変更したり、行動の順番を入れ替えたりする山登りを行いました。
提出をすると485,984,930点を得て、506人中172位、パフォーマンス1662で終了しました。
7.復習貪欲ペア解法
ここからはコンテスト後の復習です。
AtCoder公式で行っているAHCラジオでは、writerのHNN_8127さんが解説をしてくださっています。スライドだけを見ると難しく感じますが、配信では丁寧に説明をしてくれているのでおすすめです。
自分が特に理解したいと思ったのはペア解法です。コンテスト中は、怪異の出現に合わせて出力を変えるといったことを一切しないまま終わってしまいました。なので、がんばって実装したいと思います。
さて、時間が経って忘れてしまったので、一から書き直すことにします。
ペア解法は、PrussianBlueさんのペア解法の解説も参考にしました。
Editorial - 13th Asprova Programming Contest（AtCoder Heuristic Contest 070）
まず、差が(50,50)になる2つのベクトルを作ります。盤面の大きさが100なので、(50,50)だけ移動するとペアの反対側に移り、さらにもう一度移動すると元の位置に戻ります。
このように、10000マスを5000組のペアに分けることができます。
実装する際には、PrussianBlueさんの例にあった移動ベクトルをそのまま使わせてもらい、(38,1), (88,51)を使用しました。この2つのベクトルで移動した先は(50,50)だけ離れているので、ペアになっている2マスのどちらかを選べます。さらに(1,38)を100回に1回使用して、全てのペアを順番に巡回できるようにします。
次に、全マスについて、何ターン目に怪異が発生するかを記録しておきます。
現在位置から (38,1)、(88,51) だけ移動した先を比較して、怪異が先に発生する方に移動し、お札を置くことにします。
実装すると、ローカルの100テストケースの平均はスコア2,865,481.58になりました。
おおー、良い感じ。
提出すると429,629,700点で、本番276位相当の得点となりました。
さらに、すでに怪異が起きてしまっていたらお札を置いても役に立たないので、怪異の発生時刻が到着時より前だった場合には評価を下げることにしました。
すると、ローカルの100テストケースの平均は3,961,591.90になりました。
おー、そういうことなんだ！
提出すると594,399,558点、本番32位相当の得点を得ました。
8.復習ペア解法乱択
次に、移動ベクトルの値をランダムに変更し、制限時間いっぱいまで試すことにしました。各候補について貪欲法で解を作り、お札からの最短距離をBFSで更新しながらスコアを計算して、最も良かった解を出力します。新しくお札を置いたときは、距離が短くなるマスだけを更新するようにしました。
すると、ローカルの100テストケースの平均は4,116,303.76になりました。
提出をすると、619,402,048点、本番28位相当の得点となりました。
おー、うれしい。
9.復習ビームサーチ
ビームサーチにも挑戦してみました。
最初は、これまでの危険度や将来の危険度を評価に使ってみましたが、なかなか貪欲よりも良いスコアが出ません。そこで、元の貪欲法で使っていた「怪異が先に発生するマスを優先する」という評価を、ビームサーチにも取り入れることにしました。確定した危険度に、貪欲法が優先するマスを後回しにした場合のペナルティを加えて評価します。
これで、ほんの少し貪欲を超えることができました。
ビーム幅やペナルティの係数を変えながら試します。ビーム幅15、ペナルティ係数を3にして提出すると、597,384,107点になりました。延長戦118位、本番31位相当のスコアです。高速化の余地もまだまだありそうですが、評価が難しい。
今回は一旦ここで区切りとして、また時間を置いて続きをやってみたいと思います。なお、延長戦のトップは1,012,211,848点で、まだまだスコアが伸びるようです。
