【AHC033】緑コーダーの競プロ参加記録 #20

igasu_7

2024年5月29日 19:54

今回はAtCoder Heuristic Contest 033です。
ヒューリスティックでは水コーダーですがタイトルそのままです。

結果は 160 位、パフォーマンスは青色の 1818 でした。
AHCに敷居の高さを感じている方に「こんなもんでこれくらいの順位なんだ」と知ってもらえれば幸いです。

ヒューリスティックコンテストに参加しよう！

「AHCはレートが下がらないので参加するだけ得！」

コンテストによってはサンプルコードが与えられることもあります。それをそのまま提出するだけで緑perfが出たりしますし、サンプルから1点でも改善すればperfに200くらい差が出たりもします。

アルゴリズム部門のレートはあまり関係ありません。コンテストによっては開催期間が2週間くらいあったりするので気軽に参加してみましょう。

問題概要

$${N \times N}$$のコンテナターミナルと$${N^2}$$個のコンテナ、$${N}$$個のクレーンがある。$${(N = 5)}$$
クレーンは1つが大クレーンで、その他は小クレーン。
マス$${(i, 0)}$$の搬入口にコンテナがなければ$${j}$$番目のコンテナ$${A_{i, j}}$$が搬入される。
マス$${(i, N-1)}$$の搬出口にコンテナがあれば搬出される。$${i}$$番目の搬出口からはコンテナ$${iN, iN +1, …, iN + (N -1)}$$を順番に搬出したい。
上手くクレーンを操作して、スコアを最小化してね。

大クレーンは、コンテナを掴んだまま他のコンテナの上を通れる特別なクレーンです。

クレーンの操作は「コンテナを掴む/離す」「上下左右に動く/動かない」「爆破する」の8パターンです。

最終的なスコアは「ターン数$${M_0}$$」「正しい搬出口に運ばれたコンテナの転倒数$${M_1}$$」「誤った搬出口から搬出されたコンテナ数$${M_2}$$」「搬出されていないコンテナ数$${M_3}$$」に対して以下のようになります。

$$
\mathrm{score}=M_0 + 10^2M_1 + 10^4M_2 + 10^6M_3
$$

Step 0. なにもしない

今回はサンプルコードがありませんでした。
何もしなくてもスコアは得られるので、入力だけ受け取って提出します。

（Step. 1 のコードを書いたと思ったらコンテナを掴むのを忘れていたので、何もしないよりスコアが悪くなっています。）

絶対スコア：1,250,001,800 点
提出コード
https://atcoder.jp/contests/ahc033/submissions/53553278

Step 1. 左から右に

スコア計算式を見ると、順番通りでなくても、正しい搬出口でなくても、とにかく搬出してしまった方がスコアが良くなりそうです。

最初はよく分からないので、とりあえず左から右にコンテナを運びます。

gifアニメーションは公式が用意しているWeb版ビジュアライザの機能を使って生成しています。

絶対スコア：10,007,200 点
提出コード
https://atcoder.jp/contests/ahc033/submissions/53554114

Step 2. 大クレーンだけ動かす

大クレーンは他のコンテナの上を通れるので、どこからでも搬出口にコンテナを運ぶことができます。
他のクレーンはジャマなので爆破しておきます。

とはいえ、いったん搬入できるだけコンテナを搬入するまでは他のクレーンも動かします。
具体的には、以下の2つのパターンでクレーンを動かします。（動きは固定なので手入力です。）

それぞれの搬出口で最初に搬出したいコンテナが、すべての搬入口で最後に搬入される場合、次のようにクレーンを動かします。

""" こういう入力のとき """
5
x x x x 0
x x x x 5
x x x x 10
x x x x 15
x x x x 20

そうでない場合、次の図のように動かします。

コンテナを搬入できるだけ搬入した後は、小クレーンをすべて爆破して、大クレーンですべてのコンテナを正しい搬出口に正しい順番で搬出していきます。

運びたいコンテナが搬入されていない場合は、搬入口をふさいでいるコンテナをテキトーなところに移動させます。

絶対スコア：14,650 点 (平均 293 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53559270

Step 2.5. 少しだけ改善

Step. 2 では搬出可能なコンテナを昇順に搬出しています。

コンテナを1つ搬出したとき、次に搬出可能なコンテナのうち最も近くにあるものを運ぶことにします。
優先度付きキューを使います。

絶対スコア：14,097 点 (平均 282 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53565379

提出直後の順位 (32位 / 約 350 人中)

Step 3. 小クレーンを1つだけ稼働させる

いきなり小クレーンをたくさん動かすと複雑なので、クレーン$${4}$$だけ活用します。
実装をラクにするためにいくつか制約を設けました。（太字部分）

今まで通り、搬出は大クレーンの仕事とします。
小クレーンには、コンテナを搬出口に近づける仕事をさせます。

大クレーンが1つのコンテナを掴んで搬出するまでのルートをまず確定させ、その合計ターンの間に小クレーンでもコンテナを1つ動かします。

また、大クレーンのルートを小クレーンが通過しないようにします。
（大クレーンの通るマスがすべて壁マスになるイメージ。）

移動させたとき、搬出口までの距離の減少量が最も大きいコンテナを1つ搬出口に近づけます。

盤面に対する BFS を、小クレーンがコンテナを選ぶ前に1回、選べるコンテナの候補すべてに対して1回ずつ行い、どのコンテナをどのマスまで運ぶかを決定します。
BFS で各マスへの最短距離を求めつつ、BFS の探索順序をそのまま移動方法としました。

絶対スコア：11,282 点 (平均 226 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53655826

Step 4. 小クレーンの稼働範囲を広げる

Step. 3 を改善します。
実装をシンプルにするために設定していた、3つの制約を外します。

小クレーンでも搬出する。
小クレーンが、大クレーンのルートを通過してもよい。
大クレーンが1つコンテナを搬出する間に、可能なら小クレーンでコンテナを2つ以上動かす。

1つ目は、小クレーンの移動範囲を$${0 \le j <4}$$から$${0 \le j \le 4}$$に変更し、搬出時の処理を追加しました。

2つ目は、2つのクレーンを同時に動かすシミュレーションを行い、衝突などが起こらないルートを選択します。
一部の複雑な移動パターンは（実装が面倒だったので）正しい動きであっても不可と判定しました。

3つ目は、小クレーンがコンテナを1つ動かすルートを決める関数を再帰関数にしました。

そのほかにも「なるべく搬出状況が均等になるように搬出数の少ないグループのコンテナに対して優先度を上げる」、「最後の1個のコンテナに対してはさらに効率よくクレーンを動かす」など、小さな改善をいろいろしました。

絶対スコア： 9,218 点 (平均 185 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53707226

Step 4.5. 他のクレーンでもやってみる

ここまで、大クレーンと小クレーン$${4}$$の2つを使っていました。

他の小クレーン$${1, 2, 3}$$のどれかを使ったときスコアがどう変わるかを調べます。
その中で、最もスコアがよかったものを最終回答とします。

seed によっては10ターン以上効率が良くなるケースもありました。

絶対スコア：9,060 点 (平均 181 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53729250

Step 5. 貪欲を少し崩す

大クレーンが運ぶコンテナを決めるとき、マンハッタン距離ベースの評価値を各コンテナについて計算し、「評価値が最大であるコンテナ」を1つ選んでいました。

大クレーンの動きが小クレーンの動きに影響するため、評価値が最大なものを選ばない方が今後の展開が良くなることもあるはずです。

評価値の順に大クレーンの動きを5パターン選び、そのそれぞれに対して小クレーンの動きを決め、最終的な盤面の評価値が最も良かったものを採用することにしました。

盤面の評価値は「盤面にある各コンテナの搬出口までの距離の総和」をベースにし、直前の行動で搬出していれば高めに評価するなどの補正を加えました。

実は seed 0 のスコアは1割近く悪化しています。
1つのケースで悪化しても全体を見ると改善傾向にあるのがAHCの面白いところですね。

絶対スコア：8,688 点 (平均 174 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53755001

提出前は84位だったのでちょっと順位アップ。

Step 6. クレーンを3つ以上動かしてみる

ここでようやく複数の小クレーンを使うことに挑戦します。
しかし、同時にすべてのクレーンの動きを考えると大変なので、1つずつルートを決めていきます。

まず今まで通り、大クレーンのルートを先に確定させます。

次に、4つの小クレーンのうち3つを爆破したものとみなして、1つの小クレーンのルートを確定させます。

そして、残った3つのクレーンのうち2つを爆破したものとみなして、もう1つの小クレーンのルートを確定させます。
すべての小クレーンの動きを決めるまでこれを繰り返します。

コンテナを運べないクレーンがあっても、他のクレーンの動きをジャマしないのであれば稼働を継続します。
ジャマする場合は、4マス以下の移動 (340 パターン) をすべて試してみて、衝突を回避できるか調べます。どうしてもダメなら爆破します。

""" Python で340パターン生成してコピペ """
from itertools import product
for i in range(1, 5):
    for route in product("UDLR", repeat=i):
        print(f"\"{''.join(route)}\",", end = " ")

ここからはクレーンとコンテナの動きを正確にシミュレーションするため、公式より配布されているローカルテスタのコードからスコア計算の部分を拝借しました。

クレーンを5個すべて動かせるようになったので、稼働するクレーンの組み合わせを全通り試すことにしました。
bit全探索をします。

2進数の$${i}$$桁目が$${1}$$であればクレーン$${i}$$を使います。$${i}$$桁目が$${0}$$であれば爆破します。

ただし、大クレーンは必ず使用したいので、0 桁目は Step 2 で述べた「最初にコンテナを搬入できるだけ搬入」をするかしないかのフラグとして利用します。

最もスコアが良かった組み合わせの移動パターンを最終結果とします。

今、どのコンテナを運ぶか「評価値」をもとに決めています。

「評価値」と「コンテナの座標」をタプルにして優先度付きキューで管理していましたが、これだと評価値が等しいコンテナが複数あるとき「コンテナの座標」順に評価されてしまいます。

それを避けるため、ランダムに生成した整数をタプルの2番目に追加することにしました。

絶対スコア：6,418 点 (平均 129 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53801426

提出前は106位だったので、大きく順位が上がりました。

Step 6.5. 制限時間まで解きまくる

Step 6 においてランダム要素が生まれたので、時間が許すかぎり何度も問題を解いてスコアの上振れを狙います。（下振れのリスクも減らせます。）

時間内に得られたスコアのうち最も良かった移動パターンを最終結果とします。

絶対スコア：5,940 点 (平均 118 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53804086

Step 7. システムテストに向けて

もう何も改善方法が浮かびません。
せめてシステムテストで下振れを引かないようにしたいです。

ランダム要素があると同じ入力でも毎回スコアが変わります。私のプログラムではその変動幅は30ターン前後でした。

時間内に問題を解く回数を増やせればスコアのブレを減らせると信じて、プログラム全体の計算量の削減を行います。

大きな変更点として、使うクレーンの組み合わせを bit 全探索するにあたり、小クレーンを1つしか使わないパターンは最初から除外しておきます。

また、ある程度スコアが悪いパターンは途中で全探索の候補から外していきます。

問題を解いている途中でスコアの更新が無いことが明らかになった場合に処理を打ち切るなどの枝刈りも追加しました。

""" Pythonでのイメージ """
masks = [6, 7, 10, 11, 12, 13, 14, 15, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
min_scores = [inf] * (1 << N)
turn_limit = inf
cycle = 0
while not time_is_over():
    cycle += 1
    for i in masks:
        score = solve(i, turn_limit)
        best_score = min(best_score, score)
        min_scores[i] = min(min_scores[i], score)
    if cycle % 10 == 0:
        turn_limit = best_score + 25
        masks = [i for i in masks if min_scores[i] <= turn_limit]

これを最終提出としました。
いったん提出しつつも、コンテスト終了までひたすらローカルテストを回します。

ローカルテストで WA になるようなことがあれば修正して再提出するつもりでしたが、総計 78,000 ケースのテストをしてすべて AC だったので、安心してシステムテストの結果を待てました。

絶対スコア (暫定テスト)：5,867 点 (平均 117 ターン)
絶対スコア (システムテスト)： 238,776 点 (平均 119 ターン)
提出コード
https://atcoder.jp/contests/ahc033/submissions/53968209

システムテストの結果を見てみると最小で88ターンのものがありましたが、2桁スコアのケースは49個で、全体の 2.5% 程度でした。

あとがき

暫定テストは AC で 157 位、システムテストも AC で 160 位でした。

順位表を見るに

Step 0 (なにもしない) のコードを提出するとperf 515
Step 1 (左から右に) のコードを提出するとperf 791
Step 2 (大クレーンだけ) のコードを提出するとperf 1250 付近

でした。

1段目: igasu_7、
2段目: Step 2と同等のコードの方
3段目: Step 1と同等のコードの方
4段目: Step 0と同等のコードの方

「簡単なコードだけ書いてみよう」「ちょっとサンプルコード超えとくか」くらいの気持ちで、気が向いたらぜひ参加してみてください。

ではまた～。

つぶやき

AHCの感想ツイートでよく「ビームサーチ」をしている方を見かけます。
そういうヒューリスティック用のアルゴリズム、私も使ってみたい・・・。

ずっとそう思いつつも、履修のカロリーが高そうでなかなか腰が上がりません。

記事のはじめに「AHCに敷居の高さを感じている方に～」なんて毎回言っていますが、そろそろ私自身がその高い敷居を跨ぐときかも。