AtCoder Heuristic Contest 042参加メモ

• 0.はじめに
• 1.問題文
• 2.ビジュアライザ
• 3.ACするコード
• 4.LLMを使う
• 5.考察
• 6.改善
• 7.結果

0.はじめに

はじめまして、もしくはお久しぶりです。競プロ歴5年1か月のかえでです。

今回は、AtCoder Heuristic Contest 042 に参加しました。開催期間は2025年2月2日(日)19:00から23:00までの、4時間の短期コンテストです。今年からAHCの回数が増えたので、前回から2週間しか経っていません。

今はコンテスト1時間前。ドキドキしながら開始時間を待っているところです。前回は生成AIを使うと高得点を取りやすい回だったようで、自分もその恩恵を受けました。今回はどのような問題が出るかはわかりませんが、今日もまたベストを尽くしたいと思います。

今やりたいと思っているのは、スコア計算の概算です。うまく計算量を落として、高速化をしたいと思っています。

短期コンテストではあまり詳しく書く時間は取れないことが多いのですが、これを読んだ方に、少しでも参考になる部分があれば良いなあと思います。

1.問題文

atcoder.jp

• サイズ $N \times N$（本問題では$N=20$ 固定）の盤面が与えられる。
• 初期状態で、マス上には「鬼」($2N$個) と「福」($2N$個) がそれぞれ置かれており、各マスには最大1つの駒しか存在しない。
• 1回の操作では、ある行または列を選び、左右あるいは上下に1マスずらすことができる。
  • 例: 行 $i$を左に1マスずらすと、$(i, 0)$の駒は盤面から除去され、$(i, j)$にいた駒は $(i, j-1)$へ移動する( $j=1,\dots,N-1$)。
  • 同様に右・上・下へずらす操作も定義されている。
• 目的は、福を1つも除去せずに、すべての鬼を盤面から除去することである。
  • 操作は最大で $4N^2$ 回まで行える( $N=20$ のときは最大 1600 回 )。
• スコアは以下で与えられる。
  1. 全鬼除去・福無損失($X=Y=0$)なら $8N^2 - T$ ( $T$ は操作回数 )
  2. それ以外なら $4N^2 - N (X + Y)$
     （$X$ は最終的に残ってしまった鬼の数、$Y$ は除去されてしまった福の数）
• 問題の保証として、「各鬼には、上・下・左・右のいずれか1方向に福が1つも存在しない」という条件が与えられており、必ずすべての鬼を福無損失で除去できる操作列が存在する。

2.ビジュアライザ

問題文中の「例を見る」からビジュアライザを見ます。

おもしろい！

500ターンで全ての鬼が出ていき、seed0でスコアが2700でした。え、こんな良い解を見せてくれるの？と思います。（←問題文をよく読んでいないからです。うーん、反省。）

3.ACするコード

ACするコードを考えます。

「何も出力しない」が大丈夫かわからなかったので、「L 0」を出力しました。

（コンテスト終了後に「何も出力しない」=「入力を読み込んだだけ」のコードを提出してみましたがそれもACしました。）

鬼を出すことができていないので、テストケースの得点はどれも800点。150ケースあるので、120,000点が取れます。

時刻は19:17でした。

そのときのトップは438,364でした。この時間でこのスコア、早いな～と思います。

4.LLMを使う

ChatGPT o1にサンプルコードを書いてもらいました。鬼を出したら元の位置に戻すコードです。提出すると400,834が出ます。

seed0は2672のスコアが出ます。

アニメーションでseed0のビジュアライザを出力したところです。

この400,834のコードは20:02に提出しているのですが、このコードの作成自体は、もっと早い時間にできていて、手元で動かしていました。ただ、ビジュアライザを見たときに、これをどう改善したら良いかがよくわからず、考え込んでいました。一旦提出しようと思ったのが20時過ぎ。

考察がうまくいっていませんでした。

トップのスコアは465795。平均は、465795÷150=3105.3です。ここから400縮める必要がありました。

5.考察

ヒントをじっくり考えられていたらよかったなあとコンテスト後に思いました（これを書いているのはコンテスト翌日の朝です）。

さて、自分が考えたことです。

ビームサーチにしたいなあと思ったので、合法手を得て、ランダムで選択するコードを書こうと思います。戻す操作を入れなかったので、すぐに詰んでしまいました。

あれ？

（ここでもっと問題文をきちんと読んでいれば～と思いますが後の祭り）

方針を変えて、外側から近い鬼から出す貪欲を書くことにします。盤面を戻さずに全ての鬼を出すことができれば今より良いスコアが出るはずです。

• 盤面を戻さずに全ての鬼を出すこと

ChatGPTに書いてもらおうかと思うものの、福を追い出してしまったり、鬼を全部出せなくて終了しなかったりと、自分のほしいコードをすんなりと書いてくれないので、自分で実装を始めることにしました。

• 外周から鬼までの距離を調べる
• 鬼より先に福がいればINFにする
• 距離が近い鬼から出す

地道にコードを書いてデバッグをしていますが書き終わりません。もうだめかもしれない。とりあえず、すでにできている盤面を戻すコードを提出しようと思ったのが20時のことでした。400834を得ますが、このコードを改善しているわけではないので、今書いているコードを書き上げなくてはいけません。

気持ちを切り替えます。

seed0で最後の鬼が2匹残っていました。上下左右に福がいます。福を出して鬼を出そうと思います。

• 鬼が出せなくなったら福を動かす

これに大苦戦。

ビジュアライザに自分でこうなってほしいコードを書きたします。seed0のスコアが3029になりました。

このプログラムを書き上げるんだ！

もう必死です。もっと実装力が欲しい！

時計をにらみながら、焦りつつも何とか書き上げました。

時刻は21:37。得点は455,648になりました。853人中223位になり、やっと青パフォ（推定パフォーマンス）が出ました。

6.改善

やっと貪欲を書き終えました。残り時間は1時間20分。

トップのスコアを見ます。468290だったので、150で割ると、3121.93。自分は3037.63。その差を少しでも埋めたいと思います。

• 2手、先を見る

• 山登り

• 福を動かす

• １マス動かして、鬼を出すまでの移動距離が短くなるなら採用する

これを鬼を出せないときだけではなく、毎回入れるようにしました。

ついに得点が46万を超えました！

時刻は22時39分でした。

ここからはスコアを改善できずに終了しました。途中でChatGPTにビームサーチも書いてもらいましたが、うまくいきませんでした。

本当はこの辺をじっくりと考えたいところだったのですが、時間がありませんでした。

最終提出の実行時間は22msしか使えていません。

seed0でScore=3071、129ターンでした。ビジュアライザです。

アニメーションにするとこんな感じです。

7.結果

最終結果です。得点が460419点、順位は1027人中314位でした。

ヒューリスティックのRatingは、時間減衰で前回から3下がっていて、今回の結果で3上がったので、前回と変わらず1902でした。

おもしろい問題だったので、この後も復習をしたいと思います。みなさんの解法を見ていて、盤面の評価は入れたかったなぁと思いました。

2025年2月3日の午後9時からは感想会スペースを開く予定です。また、2025年2月5日の午後8時からはAtCoderLiveでAHCラジオもやる予定です。

次は2025年2月14日からRECRUIT 日本橋ハーフマラソン 2025冬（AtCoder Heuristic Contest 043）があります。相性の良い長期コンテストなので、次こそは良い結果を出したい！

atcoder.jp

簡単な振り返りにはなりますが、これで終わりたいと思います。

ここまで読んでくださり、ありがとうございました！