0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年半のかえでです。
これは、2025年8月23日土曜日午後3時から午後7時までの4時間コンテスト「AtCoder Heuristic Contest 052」に参加したときのメモを元にした簡単な参加記と、その後の復習を書いたものです。
1.問題の概要
ロボット10台を1台のコントローラーで動かして、床全体にワックスを塗る回数を最小化する問題でした。
2.コンテスト参加時の記録
15:10 ロボット0(1台)だけを動かすプログラムを書いて提出します。
下記はseed0のビジュアライザです。ロボット1台を使用しても、2×Nの2乗=1800ターンあれば必ず行って戻ってくることができ、全面を埋めることができます。
テストケースは150個で、1ケースの得点が2700-1800=900なので、900×150=135,000の得点を得ることができました。
コンテスト時には、terry_u16さんの並列テスト実行ツール、pahcerを、Yunixさんのツールで管理して使用しました。
terryさんのpahcerを使ったテスト管理ツールpahcer-studioを公開しました。https://t.co/Emht9LbMk1
— yunix (@yunix91201367) 2025年7月3日
pahcerの実行・ビジュアライザの表示・テストケースの分析などをできるようにしました。
Electronを使ったアプリなので動かすのがちょっと大変かも。
(あとバグってたらごめん) pic.twitter.com/kqwMislwXZ
AHCテストケース実行ツールpahcerの使い方 - TERRYのブログ https://t.co/JuMqEVC9ar
— TERRY (@terry_u16) 2025年7月30日
pahcerの使い方講座を作成しました！
最近新機能も入りましたので、金曜日から始まるAHCのお供にご活用くださいー
最初に設定を行い、ビジュアライザに必要なファイルもダウンロードして、準備完了です。
複数のロボットを動かして様子を見ることにします。まだ床面は全部塗れていません。
（塗り残しをBFSで距離の近いロボットが取りに行くを試したところ。メモが残っていなくてよく覚えておらず。）
100テストケースを実行します。
yunixさんのツールで100テストケースの前回の結果と今回の結果を比較します。黄色の折れ線グラフがロボット１体で全部塗りつぶしたときのスコアです。今回の結果（緑いろのグラフ）を見ると、塗りつぶせたものは高得点になっていますが、まだ黄色より得点の低いテストケースが見受けられます。全部塗り潰せていないテストケースがなくなるよう、改善する必要がありそうです。
15:43 順位表のトップが365121なので、50で割ると1ケース2434。全ケースをきちんと塗ることができれば、そこまで遠くない値に見えました。
しかし、最後の塗りつぶし部分がうまくいきません。下記を試します。
- 終盤で「近いロボットが最後の塗り残しを担当」するように、未清掃セルが閾値以下になったらロボット↔セルの距離最小マッチング（貪欲）に切り替える
- 未清掃が少なくなったら、ロボット↔未清掃セルの距離最小割り当てを行い、各ロボットは自分に割り当てられたセルへ最短で近づく一手を希望します。候補セルが多い場合は、ロボットの最近傍セル＋ロボットから最も遠いセル（分散性）を混ぜて最大M個に絞り、そこに対してハンガリアン法を適用します（M≤10なのでO(M^3)は軽い）。
16:18 合体して提出
まだ、貪欲しかしていないので、ビームサーチ、ランダム生成を試したいと考えます。
ビームサーチを行います。
全面塗りつぶしても動いているテストケースがあったので、終了判定を追加します。また、同じ動きを繰り返してしまうので、ランダム移動を入れることにします。
100テストケースの結果を見ると、だいぶ塗りつぶせるようになってきたことがわかります。
16:42 ビームサーチ解を提出します。
塗り残しが10個まで減ったら、完全に割り当てることにして、1個ずつ塗りつぶすことにします。
やってみたところイマイチだったので、戻します。
うーん、これ、貪欲が強いんじゃないかな。
ここまでビームサーチで進めてきたのですが、うまく改善できません。別の解法を試したくなってきました。
トップは378040、1ケース平均2520です。
30×30=900マスを10のロボットで塗るので1体90マス。
3N^2T=2700-2520=180
うーん、無駄がない。
シンプルな解法を考えます。
- (0,0)に近いロボットを(0,0)に向かわせます。蛇腹状に塗ります。
- すでに塗ったマスに到達したら、まだ塗っていない遠い方からロボットを割り当てて塗ります。
うん、こっちの方が良さそう。
実装してみると、100テストケースの平均は1994になりました。これまでのベストが平均2164だったので、伸びしろがありそうです。
塗っていないマスの検索を(0,0)から始めるように変更します。
うん、良さそう。
下記のグラフで青色が今のプログラムです。これまで解消できなかった塗り残しが全てのテストケースでありません。
100テストケースの平均は2108になりました。
(0,0)から始めるのをやめて、下記を実装します。
-
蛇腹：水平方向に行ける限り進み、壁で止まったら1段下＆折り返し方向に進む
-
埋め残し：毎回1回だけマルチソースBFS → 到達可能な未塗のうち最短距離（同距離は
(i,j)昇順）へ最短路で移動
100テストケースの結果を見ます。よくなったものと悪くなったものがありそう。
さらに改善すると平均が2292になりました。（曲がることにペナルティを追加）
100テストケースの結果を見ると、ほぼ、ベストを超えたように思います。
18:10 提出 平均2287.2
最初のビームサーチ解法を追加し、両方を比べて良い解を出力するようにソルバー２つを合体します。
18:24 提出 平均2333.4
- 「ボタン割当の自動チューナ」と「複数レイアウト並列トライ」を試します
18:34 提出 平均2364.1
（さらに何かを試したと思うのですがメモをしていなくてよく覚えておらず。）
18:48 提出 平均2372.9
うーん、これ以上スコアを上げることができません。
そして、コンテストが終了しました。
3.結果
最終結果は、355,928点、819人中231位でした。かろうじて青パフォだったものの、Ratingは時間減衰で減っていたため+4でも前回と変わらないRatingとなり、Highestを更新することはできませんでした。
4.復習1 蛇型解を書く
感想会スペースでtomerunさんから聞いたビームサーチの評価値、タイブレーク時に「同じ方向に加点する」評価を追加したら、355928(231位)→362730(152位相当)、平均2418.2になりました。
このような評価を思いつきたかった…。
さて、公式のAHCラジオを見て、復習を開始します。
今回の解法で強かった蛇型に塗りつぶす解を試します。
解法としては、ランダムでキーを割り当て、ジグザグに動いて長方形に塗ります。
本当にランダムにキーを割り当てると、"00000021111112"のように塗っても、階段状に塗られたりして、四角に塗ることができません。ジグザグに動くようにするため、最初の3つのボタンを下記4種類にして、そのどれかをランダムで選びます。
- 最初の3つのボタンを、UDR、DUL、LRD、RLUの4種から選ぶようにし、4つ目以降のボタンをランダムで割り当てます。
- 4つ目以降のボタンで6歩ランダムで動いたのち、最初の3つのボタンを用いて、"00000021111112"を繰り返して四角に塗りつぶします。繰り返し回数は変更できるようにします。
- 時間一杯ランダムに解を生成して、一番スコアの良いものを出力するようにします。
山登り前に貪欲解を確認します。何回かデバッグして、下記のようなビジュアライザになりました。
良さそう。
すぐにLLMに実装させそうになる気持ちをこらえて、自分でコードを書きます。この頼り癖が自分のプログラミング力を低下させているに違いありません。
山登りをします。18万回試行していますが、全部塗りつぶすことができません。
最初のランダム移動の歩数を変化させたり、ジグザグの幅等を変化させて試しますが、塗り残しが出ます。120ターンで塗ることを試していたので、140や160など重複を増やしてみますが、それでもダメでした。
塗残しは貪欲に埋めてしまった方が良いのかもしれません。
塗り残しを近いロボットが埋めに行く貪欲を追加し、やっと全てを塗りつぶすことができました。
seed0のスコアは2440になりました。
100テストケースの平均は2409.7になりました。
提出をします。362324で、平均2415.5でした。しかし、これまでのベストを更新することはできませんでした。
試行回数が1700回ほどなので、貪欲が重すぎるのかなぁ。
うーん。
ああ、そうか。全部毎回ランダムで構築しているからいけないのかも。ロボットを１つ選んで変更する要素を入れてみようかな。
うーん、良くなりません。
さて、ここまでの解を作るのに、すでにかなりの時間を費やしているので、直接wataさんのプログラムと自分のプログラムの差を調べることにします。
5.復習2 答え合わせ
wataさんのRUSTのプログラムと自分のプログラムの違いをLLMにたずねます。
- 重複排除や多様性の確保（自分はしていない）
- 長さL=120固定（自分は可変）
- 固定キーで動き優先（自分はランダム）
- 全点BFSで距離前計算（自分は都度BFS）
なるほど。真似してみます。
「絶対方向キー（6..9）固定」と「L=120固定の準全探索（d0..d4の割当て）」を取り入れます。
すみません。LLMの力を借ります。
プログラムを実行してみます。
思わず、あっ！と目を見開きました。
seed0がスコア2574になっています。
そしてビジュアライザが、う、美しい…。
え、何で？
100テストケースの平均は2534.2でした。提出します。
本番4位相当、延長戦でも16位のスコア380750が出ました。
もう自力ではないので、参考外の成績です。
以下、LLMに質問した回答です。
どこが悪さしていたか（症状→原因→影響）
目的地まで“単独で動かせる”ボタンが実質なかった
原因：行6..9を「全ロボU/D/L/R」に固定していなかった。
pick_button_forは“他ロボが'S'”の行を探すけど、初期cに'S'が少なく、副作用ゼロ行がほとんど見つからない。影響：狙った1体だけ動かしたいのに他も動いてしまい、最短路が崩れる→振動・遠回り・Tが伸びる。
押下列とキー割り当てが“別々にランダム”
原因：先に
cをほぼランダムで作り、あとから蛇腹風opsを流す構造。影響：押下列に対して「どのロボがどの方向を押すと一番増えるか」を見ておらず、同じ手数でも新規踏破が伸びにくい。
(d0..d4) の準全探索が無い
原因：
ds=[d0..d4]の組み合わせをロボごとに吟味せず。影響：同じL=120でも「増え方（gain）」の差が大きく、初期の面積稼ぎで負ける。
穴埋めBFSが“副作用前提”になっていた
原因：
pick_button_forで見つからないと、行0..3にフォールバックし、その列だけ上書き（他列はそのまま）。影響：その行を別の場面で押したときに他ロボも動く危険が残り、局所修正が後で広域副作用に化ける。最短路の安定性が悪い。
候補を貯めず、短縮フェーズが無い
原因：毎ループ「1本作ってスコアが良ければ更新」型。
影響：良い初期解が出ても、その解を手数最小まで詰める工程が無く、Tが縮みにくい。
評価関数が“同時に2つ”を追ってブレやすい
原因：
score_calcは「全踏破なら 3N^2−T、未踏ありなら N^2−R」。影響：構築中はR重視、終盤はT重視で、探索の指針がぶれやすい。Rustは「構築→T最小化」にフェーズ分離して明確。
‘S’が全体に少ない
原因：行3..K−1もU/R/D/Lを満遍なく埋めていた。
影響：副作用ゼロの行が作れず、
pick_button_forが機能しづらい（1と同根）。いまの修正でどう治ったか
行6..9＝絶対キー固定 → 最短路を副作用気にせず一直線で押し込める。
L=120固定＋(d0..d4)準全探索 → 初期の面積稼ぎが大幅に安定。
穴埋めは絶対キーのみ → ルートがぶれず、Tが縮む。
まとめ
まとめると、「単独制御のキーが無く、副作用を抑えられない」「押下列に対して方向割り当てを最適化していない」「短縮フェーズが無い」の3点が主因でした。いま入れた2つ（絶対キー固定＋L=120準全探索）で、そのボトルネックがほぼ直撃で解消されています。
上記の回答はちょっとピンとこないところがあったので、自分が感じた違いです。（これが正しいかどうかは責任が取れないので、自分で調べていただけると助かります。教えていただけるとさらにうれしいです。）
- 最初のランダム移動が2方向に限定してランダムで最大10+10移動している
- 私はランダムで4方向から選択したので、初期位置からの移動があまりなかった
- 各ロボットのベストキー配置を全て調べている
- Lを120と限定して蛇型のジグザグを最初に決めている。そのかわり、各ロボットのベストキー配置を全て調べている。
うーん、すごいなあ。
ビームサーチも焼きなましも使わないで高スコアを出すことは、全然簡単じゃなかった。
ここからさらに得点を伸ばす方法はゆっくりと考えたいと思います。
一旦、今回の復習はここで終わりたいと思います。難しかった…。
