- 0.はじめに
- 1.問題文を読む
- 2.ビジュアライザを見る
- 3.最初の提出
- 4.初日の考察（手動でビジュアライザを動かしてみる）
- 5.前日のコードの確認（100テストケースを試す）
- 6.邪魔なコンテナを動かす
- 7.小クレーンを動かす（考察）
- 8.問題文を誤読していた！
- 9.小クレーンを動かす
- 10.必要なデータ構造
- 11.停滞、そして停滞
- 12.もう一度書き直す
- 13.最後に提出した日を遠く思い出す
- 14.バグからの脱出
- 15.小クレーンの動きを変える
- 16.仕切り直し（評価関数を考える）
- 17.再びビジュアライザを見ながら考察する
- 18.コンテスト10日目(2024年5月26日)
- 19.小クレーンを増やす
- 20.終わりに
- 21.最終結果（2024年5月30日更新）
0.はじめに
はじめまして、もしくはお久しぶりです。競プロ歴約4年半のかえでです。
今回は、トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）に参加しました。開催期間は2024年5月17日(金)19:00から2024年5月27日(月)19:00までの11日間の長期コンテストです。
さて、今日は2024年5月15日、木曜日の夜です。久しぶりのコンテストなので前日からわくわくして待っています。気になっているのはchokudaiさんがwriterなこと。どんな問題が出てくるのでしょうか。きっと難しくて最初は全然わからないのだと思います。少しずつ考察を進めて、何かをつかめればいいなあと思います。今回もまた、参加記を書きながらコンテストに参加したいと思います。
そして、この参加記を読んでいる方にヒューリスティック・コンテストとはどのようなことをするコンテストなのかを知ってもらえたらうれしく思います。また、AHCの解説には誰でも解法を載せることができるので、コンテストに参加していた方にはぜひ解法や参加記を載せてもらいたいと思っています。一人一人が違う解法で得点を得ることができるのがヒューリスティック・コンテストの楽しさの一つなので。
1.問題文を読む
問題名は「Container Handling with Cranes」。概要を書くとこんな感じです。
- N×Nマスのコンテナターミナルがある（N=5で固定）
- 0から24までの番号がついた25個のコンテナを指定された順番で搬出する
- 搬出には大クレーン1台と小クレーン4台を使う
- 大クレーンはコンテナをつかんだ状態でどこにでも移動できる
- 小クレーンはコンテナをつかんだときには空きマスにしか移動できない
- コンテナは同じマスにいることや、すれ違うことができない
- クレーンには下記操作を指示できる
- コンテナをつかむ
- コンテナをはなす
- 隣接マスに移動する
- その場にとどまる
- 爆破する（その場から消す）
- スコアを最小にしたい
2.ビジュアライザを見る
問題文を読んだあとは、問題文中の「例を見る」のリンクからビジュアライザを開きます。文字の番号が小さい方のコンテナが青色、大きい方のコンテナが赤色になっているようです。
こういう問題はうまくソートできれば良さそうに思うものの、大クレーンと小クレーンの使い方とか、爆破といった見慣れない操作があって何ができるのかよくわかっていません。少しずつ考察をしていきたいと思います。
3.最初の提出
帰宅しながら問題を読んで、ビジュアライザを見ていました。
まずは一番簡単なACするコードを考えます。
順番を考えずに左から出てきたコンテナをつかんで右側の搬出口に運ぶことにしました。
つかんで(P)右へ4マス進み(RRRR)、離して(Q)左に4マス戻る(LLLL)。これを各クレーンが5回ずつ行います。最後はコンテナを離して終了します。
コピペで下のような出力を書いてText (cat 8.32)で提出します。
PRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQ
PRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQ
PRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQ
PRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQ
PRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQLLLLPRRRRQ
無事ACしました。絶対スコアは10007200、相対スコアは72,086,780。順位表の30位には同じスコアがたくさん並んでいました。
4.初日の考察（手動でビジュアライザを動かしてみる）
ビジュアライザに手で出力を打ち込みながら考えます。まずは案1のコードを書いてみたいと思います。
（案1）
- 1から4番目のクレーンを使ってコンテナを移動して一番小さい番号のコンテナを掘り起こす
- 0番目のクレーンを使って搬出する
待機場所が多くあるので、何となくこれで順番通りに運べ出せそうな気がしています。
それとも案2の方が楽かな。
（案2）
- 一時待機場所に20個コンテナを並べる
- 0以外のクレーンを全部爆破する
- 一時待機場所にあるコンテナの中で小さいものから順に運び出す
案2を手動でビジュアライザを動かして行ってみます。0から12までは何の苦労もなく運び出すことができました。コンテナ13が配置されるように塞いでいるコンテナ15を下にずらします。
同様に20のセットを妨げているコンテナ21を右に動かすと、その後は問題なく最後まで順番に運び出すことができました。
思ったよりも簡単そうなので案2を実装したいと思います。現在のトップとのスコア差が約718倍、最初の提出のseed0のスコアが200246で今の方法286で割ると700倍。同じことをしていそうな感じがします。
（実装中・・・）
書きました。時刻は2024年5月17日の午後11時くらい。前の行から2時間半が経過しています。うーん、実装が遅いかも…。
seed0のアウトプットを確認して手動と同じスコア286が出たので提出をします。
結果はWAで0点でした。50テストケース中、3テストケースでWAが出ていました。
相対スコアは提出前の49,098,794から4,040,664,118になりました。順位は94位から59位に上がりました。相対スコアが上がったものの順位はそこまで上がらないなあと思います。
今日はここまでにして寝たいと思います。まだseed0しか見ていないので明日は100テストケースを試して考察を進めたいと思います。
寝る前に順位表のトップを見ます。トップとの相対スコアの差は12倍でした。
5.前日のコードの確認（100テストケースを試す）
100テストケースの結果です。スコアは問題ページの下部で提供されているWindows用のコンパイル済みバイナリを使用して出力します。
自分はWSLを使用しているので、こんな感じで実行した結果をテキストファイルに落としています。
./a.out <0000.txt >output_0000.txt
出力テキストが作成出来たら提供されているvis.exeを使います。
vis.exe 0000.txt output_0000.txt
コマンドプロンプトにはACの場合はスコア、WAの場合は理由が表示されます。
ACの場合：
Score = 286
WAの場合：
Crane 0 moved out of the board. (turn 186)
Score = 0
点数が悪いことにがっかりしながらも正直ほっとしました。
300くらいのスコアを出しながらトップと10倍以上の差があったらどうしたらいいんだろうと悩んでいたところでした。というか、逆にこれ、きちんと小クレーンを活用したらターン数はまだ半分以上削れると思っているので、チャンスかもしれません。
んー、がんばろう！
公式のビジュアライザでは複数の出力を切り替えてみることができるのでフォルダをアップロードします。
seed1ではコンテナ18の後にコンテナ19をとばしてコンテナ20を選んで運んでいました。バグってる～！1個とばして運んだせいで、スコアが1000284になっていました。
もったいない。
他も見ますが、取れるコンテナが残っていました。そして100テストケース中11個しかきちんと運べていなかったことがわかります。
コードを修正します。
バグは簡単に見つかって100テストケースのWAもなくなりました。案2が成功しているケースも23個になりました。
提出をします。
わくわく。
無事ACしました。
相対スコアは提出前の1,800,109,751（1日で相対スコアが半分以下に下がっていました）から4,137,093,494に上がりました。順位も149位から128位に上がりました。
移動部分をきちんと書けばこの方法であと1.5倍、10G(100億)のスコアにはできそうです。順位表はそこからまだ5倍。今の状態なら20Gは目指せそうなのでまずはがんばって全て正解を取るコードを書きたいと思います。
6.邪魔なコンテナを動かす
一番左にコンテナがあって邪魔な場合には上右下にスペースがあれば動かすということをしました。最短でスペースがある場所から1個ずつずらしてスペースを確保するようにしたいと思います。
ここは「つかむ・はなす」といった動作を加えて最短を調べるコードにすればもう少しスコアが良くなると思われるのですが、今は省略します。
ちょうど良いseedがありました。seed3のビジュアライザです。図で表すとこんな感じ。1を掘り起こすまでに3個のコンテナを移動します。
書き直しましたが成功したのは42個。まだ半分以上バグらせているのですが記録もかねて一旦提出します。ACしたのは50テストケースのうち半分以下の24ケースだけでした。
相対スコアは提出前の4,064,656,262から6,673,744,262と約1.5倍になりました。順位は156位から少しだけよくなって150位になりました。
全部ACすると14Gくらいにはなりそうです。
バグっているのは空きマスがない状態で0が一番左にある状態でした。結構な確率(20%)で起こりそうです。うーん、この解法の限界を見た感じです。
とりあえず右端にあるコンテナのうち、一番ペナルティが少ないものを搬出することにします。
（実装中・・・）
バグが100テストケース中24個まで減りました。まだ0にならないけれど、記録として一旦提出します（コードと得点の対応が取れるので提出自体が記録として有効だと思っています）。
相対スコアは、提出前の155位6,683,190,910から136位10,262,698,801に上がりました。
時刻は午後3時。疲れたので休憩します。
お昼寝から起きて、また少しずつデバッグをします。約1時間でやっと100テストケースで正の得点が取れました。
提出します。
無事ACして、絶対スコアは17336になりました。平均スコアが約347ときちんと案2を行っていそうです。
やったー！
相対スコアも提出前の166位9,786,117,343から115位11,879,787,153になりました。予想(14G)まで相対スコアが上がらなかったのはトップが伸びているせいなのかなぁ。後ほど考察したいです。
7.小クレーンを動かす（考察）
次にやることは早々に爆破していた小クレーンを使って大クレーンをサポートすることです。たとえば、
- 今あるコンテナを右詰めにする
- 今あるコンテナを並び替えて取り出しやすくする
みたいなことをすると今よりもターン数を短くできそうです。次のコンテナを持ったまま待機するみたいなことも良さそうなのですが、実装がピンとこないので後で試してみたいと思います。
小クレーンがたくさんあると経路が難しくなりそうなのでまずは1個だけ残すことにします。大クレーンが小クレーンのある場所を通りたいときはぶつかってしまうので小クレーンがよけることにします。
8.問題文を誤読していた！
2024年5月19日、コンテスト3日目の朝です。小クレーンを動かすことを考えていたのですが、やっぱり転倒数のペナルティが痛いので別の方法に変えた方が良いのではないかと悩んでいました。再度問題文を読み直していてふと気がつきました。
別にコンテナ0から出さなくてもいいんじゃない？
各行の搬出口の一番小さな値だったら搬出してしまっても良さそうです。ペナルティにも前のコンテナ番号との差分がないので、「指定された順番で搬出する」とは0から出すことを意味していないことがわかりました。
そうしたらわざわざ0を掘り起こすためにペナルティの低いものを搬出するなんてこともしないで良さそうです。ペナルティがなくせたら今より平均は1割以上スコアが良くなるはずで、まずはこれを修正したいと思います。
実装内容をもう一度書き出します。
- 5つのクレーンで盤面に20個のコンテナを並べる
- 小クレーンは爆破する
- コンテナは大クレーンが25個運び出す
- 大クレーンが今いる場所から一番近いペナルティのないコンテナを探す
- コンテナに移動する
- コンテナをつかんで搬出口に移動する
おー、何かシンプルになったし、掘り起こしをする確率もほぼ0に近くなった気がします（掘り起こしが必要なのは、25個あるコンテナのうち並べられていないコンテナ5個が0,5,10,15,20のときだけなので、C(25,5)通りあるうちの1通りなのでものすごく小さな値になりそうです）。
さて、実装しなおしてみたら、コンテナを右詰めに移動するクレーンがあった方がいいなと思いましたが、大クレーンで邪魔なコンテナを動かす方が簡単そうなのでそれを加えたいと思います。
書きました。詰まっているとき邪魔なコンテナを上右下のどれかにずらせるかを判定して動かしただけなので、100テストケース中2ケースは全部運び出せていません。それでも他は300ターン以内に終了していました（転倒数のペナルティがない状態で終了していると予想される）
提出をします。
絶対スコアは悪くなり9013653になりましたが想定のうちです。
ドキドキしながら順位表を見ます。相対スコアは提出前の186位10,497,566,062から90位12,273,019,365に上がりました。ついに久しぶりの2桁順位になりました。
やったー！
3日目に誤読に気がつけるなんて、成長したなあと思います。
バグも修正しました。100テストケースの平均スコアは以前の347から274まで減少しました。おー、ここからが小クレーンを使う勝負だなと思います。
30分経つのを待って再度提出をします（長期コンテストでは30分に1回という提出制限があります）。
絶対スコアは13766になりました。
順位表をリロードして、結果を見ます。
おおっ！驚いて声が出ます。
相対スコアは12,534,040,888になり、順位が58位になりました。
うれしい！
これはチャンスなのではないかな（2回目）。
それでもトップとの差は4倍。70ターンくらいで終わっていると思うとすごいなと思います。少しでも差を縮められるようにがんばりたいです。
9.小クレーンを動かす
- 右詰めにする
- 一番右に搬出するコンテナがあるときにコンテナをつかんで待機する
- コンテナを搬出口近くに集める
- コンテナを並び替える
大クレーンがいろいろな場所からコンテナを運び出す際にできる小クレーンのサポートは、書き出しただけでもいろいろとあります。
まず他のクレーンを動かすために1手ずつ動かすコードに変えたいと思います。これまでは現在地点から目標地点に行く関数を作っていました。このコードの書き方だとぶつかるときの対処が面倒な気がします。
1ターンで複数のものを動かすとき、コードを書く難易度がぐっと上がると思っています。それは自分の好きなCodinGameというボットAIプログラミングコンテストでよくある設定なので経験済みです。小クレーンを爆破できるというのが、もしかしたら初心者向けに追加されたルールなのかもしれないと思いました。
さて、コードを書きます。
（実装中・・・）
面倒になってきたので、大クレーンの１回の動き（今いる場所からコンテナを探して搬出するまで）を記録して、その間に小クレーンが空きマスの左隣のコンテナを右に動かせるかを試すコードに変えたいと思います。
（実装中・・・）
これも面倒でした。何とか大クレーンの邪魔をせずに逃げ回る小クレーンを1個作りました。
（実装中・・・）
これもいまいちでした。ちょうど取ろうとしているコンテナを動かしてしまうという残念な事態が発生。やっぱり同時進行でないとダメそうです。
こうして日曜の夜が終わってしまいました。
10.必要なデータ構造
あまりにもバグらせているので必要なデータ構造が足りない気がしてきました。今管理している内容です。カッコ内はサイズです。
- 各行の搬出したいコンテナの番号（N）
- 現在の盤面（N×N）
- コンテナが一時置き場に出されたかどうか（N×N）
- コンテナを搬出したかどうか（N×N）
- 大クレーンと小クレーンの動き（ターン数×クレーン数×x座標とy座標）
- 答え（ターン数×クレーン数）
追加しようと思っているものです。
- 大クレーンが今運ぼうとしているターゲットコンテナ番号（ターン数×コンテナ番号）
- 大クレーンがターゲットコンテナを動かしたターン数（N×N）
- コンテナの位置（ターン数×N×N）
これがあれば衝突を避けられるはず…。
うーん、各ターンの盤面を記録するようにした方が良い気がしてきました。
11.停滞、そして停滞
やっとseed0を見ながらデバッグして最後までスコアが出ました。本日は火曜の夜。丸二日格闘していました。
seed0では282ターンかかっていたものが242ターンで終了しました。
しかし100テストケースを試してみると、ACしたのは27ケース。大クレーンと衝突していました。
100テストケース中58ケースがACするようになりましたが、どこか本質部分がいまいちな気がしています。
12.もう一度書き直す
コンテスト5日目の夜です。現在のトップです。
私はといえば3日間提出ができず、順位は170位まで下がってしまいました。
さて、気を取り直して考えます。
私のコードでWAが出る理由は、大クレーンと小クレーンが衝突してしまうこと、そしてあるべき場所にコンテナがないことです。バグらせている理由は、コンテナをつかむで1ターン、コンテナを離すで1ターン使っている部分だと思っています。その場所にコンテナがあるけどつかんでいるといったときの定義が曖昧なせいだと思っています。
書いていたら少し思考が整理されてきましたように思えます。
もう一度ステップを見直してコードを書き直したいと思います。
- ターン数
- 各クレーンの座標
- 各クレーンの状態（コンテナを持っているかどうか、何番のコンテナを持っているか）
- 搬出したい各行のコンテナ番号
- 現在の盤面の状態（コンテナ）
- 現在の盤面の状態（クレーンの位置）
- 出力（各クレーンの動作文字列）
- 各クレーンの目的地と目的コンテナ番号
- 搬出されていない残りのコンテナ数
これでどうだ。足りているかな。毎回何をするかを評価関数で決めたいと思います。
- コンテナを持っていないときは搬出したい今いる場所から一番近いコンテナ番号の評価を高くする（大クレーン）
- 搬出したいコンテナの位置に来たらコンテナをつかむ（大クレーン）
- コンテナを持っているときは最短で搬出口に行く（大クレーン）
- 搬出口に来たらコンテナをはなす（大クレーン）
- コンテナを持っていないときは一番右端にすぐに搬出できるコンテナ番号の評価を高くする（小クレーン）
- コンテナを持っていないときは今いる場所から一番近い右隣が空きマスのコンテナ番号の評価を高くする（小クレーン）
- コンテナを持っているときは右隣に移動する（小クレーン）
- コンテナを持っているときに空きマスに来たらコンテナを置く（小クレーン）
- クレーン同士がぶつかる、もしくはすれ違う場合は評価をマイナスにする
これでいけるかなあ。うまく書ければスコアアップ間違いなしなのでがんばります。
13.最後に提出した日を遠く思い出す
書き直しました。2024年5月23日木曜日の夜です。バグらせ続けて、デバッグをし続けました。ついにseed0でACするコードが書けました。100テストケースをまわして、公式のジャッジツールでスコアを見ます。
100ケースが全てWAでした。出力された文字列がなぜか最後にQQとQが2つ並んでいました。
なぜ？
修正します。100テストケースのうち28ケースでWAが出ました。
WAが出たseed71のビジュアライザを見ながら修正します。
WAが22個になりました。
WAが出たseed2を書き直します。
WAが20個になりました。
希望が見えたと思ったのに、100テストケースのWAが0個になりません。
果てしない…。最後に提出したのはいつのことだったでしょうか。
ただ、つらいはつらいのですが、面白いといえば面白いのです。あきらめたくない思いでいっぱいです。
ひたすらデバッグを続けます。ブログも書かずにデバッグをしていたので、ビジュアライザでダメな個所を列挙した方がよいかもしれないと思い始めました。
列挙するぞ！と思ったら、急にWAが1個になりました。コンテナを持っているときに目標となるコンテナを探しなおしていたからでした。そして最後の1個はseed82。
同じコンテナ20を目指していったり来たりしていました。
解決方法が難しいので、いったん提出することにします。100テストケースの平均は274.3から223.7に下がりました（ターン数と同じ値がスコアになる）。
提出前の相対スコアは11,790,931,254で、914人中198位まで下がっています。50ケース中3ケースがWAでした。うーん。
相対スコアは12,284,599,546になり、172位になりました。上がったのはうれしいものの、もっと上がると思っていたので、残念に思います。
3個のWAを修正したら6%上がって13Gに届くかもしれません。
先ほどのseed82ですが、これまでは大クレーンを優先することにしていましたが、遠い方に止まってもらうことにします。
これはうまくいくようになったものの、他でWAが出るようになりました。
一進一退の状況が続きます。
お風呂から出てきました。最初の解法と2番目の解法を組み合わせて全てACする方法にしたいと思います。
14.バグからの脱出
全部がうまく解けなくてもいろいろな解法を組み合わせてスコアを更新できれば良いとやっと思うことができました。がむしゃらにデバッグをしているときには、なかなかこの発想にたどり着けません。
2つの解法のうちスコアの良かった方を採用するコードに修正しました。
やっと100テストケースをローカルで試して全てACすることができました。
提出をします。
ACしました！絶対スコアは11505、相対スコアは提出前の180位、12,257,439,314から137位、14,169,173,986に上がりました。
やったー！
そして、やっと一息つくことができました。
今日は早く寝たいと思います。（連日遅くまでデバッグをしていました）
seed0ではScore233が出ています。
15.小クレーンの動きを変える
次に何を改善するかを考えます。下の3つを考えました。
- 初期配置を変える
- 小クレーンを右詰め以外に動かす
- 小クレーンを増やす
初期配置を変えることに関して、17ターンで20個並べるメリットの方が大きい気がしたので今回はパスします。小クレーンを増やしたいと思うものの、それよりはまず小クレーンの動くを洗練させたいと思いました。なので、小クレーンを右詰め以外に動かすことを考えます。
たとえばseed0の165ターン目、小クレーン4はコンテナ16を右に1マス詰めて終了します。しかし、搬出までのルートが全て空いているので持っていくことができます。
小クレーンの動きを変えてこんな風に搬出口まで持っていければ良さそうです。
実装してみます。
ところで、コンテスト8日目の順位表です。トップは接戦のようです。自分とは3.5倍差なので65ターンくらいで終了しているのでしょうか（計算合ってる？）4つの小クレーンを爆破しないで使えるようにできたらいいけど難しそう…。
割とあっさりと書けました。seed0は214になりました。100テストケースを試すと、WAが8個出ました。あまり変わらないかなあと思いつつ、大クレーンのみ解法と組み合わせて一度提出することにします。絶対スコアは11140になり、前回よりも3%ほど下がりました。相対スコアは提出前の157位、14,100,945,855から153位、14,580,578,174に上がりました。
WAが出たところを見直します。見るからにループしていそう。
穴をふさぐように評価関数を変更すると他のところであらたなバグが出ます。
お風呂に入ってゆっくりと考えました。
そうか、相手のいる場所と目的地の間に自分がいるとダメなのだなあと気がつきます。間にいる方が道を譲ることにします。
よくなった！と思ったのですが100テストケースを試すとWAが増えていました。
その後3つの解法で一番よかったものを出力するようにしたいと思いますがこれもまたバグらせてしまいました。
えーん、どうしよう。考えながら眠りたいと思います。
16.仕切り直し（評価関数を考える）
2024年5月25日土曜日の朝です。評価関数の漏れがあるのかもしれません。煩雑なコードになってきたので、書き直したいと思います。
まずは合法手の見直しです。
- 大クレーンと小クレーンの違い
- 大クレーンはどこにでも移動できる
- 小クレーンは空きマスにのみ移動できる
あとは一緒にできるはず。
- クレーン同士は同じ場所になったり、すれ違うことができない。
この辺があやしいのかなぁ。
評価関数を書き終えて問題なさそうなので提出します。絶対スコアはほんの少し小さくなり11063になりました。相対スコアも14,695,785,247になり微増。順位は181位でした。
100テストケースで小クレーンを使ったバグっているテストケースを見ながら修正します。再提出をすると、え？得点が18010579になりました。相対スコアは提出前の184位、14,675,397,672から176位、15,006,827,282に上がりました。
調べてみると、大クレーンのみの解法と組み合わせる際の比較方法を大クレーンの文字列の長さで行っていたため、小クレーンが最後にコンテナを運ぶ部分をカットしていることがありました。修正して提出します。
絶対スコアは10581、相対スコアは提出前177位、15,003,227,311から171位、15,217,745,152になりました。もう微妙すぎて言うことがありません。
17.再びビジュアライザを見ながら考察する
どうしたら良くなるのだろう？
ビジュアライザを見ながら考えます。seed6のを見ていたら、小クレーンが1を運び出すことができるのになあと思います。コードを書き直して提出してみますがもうほとんど結果は変わりませんでした。
18.コンテスト10日目(2024年5月26日)
コンテスト10日目の朝です。明日が最終日ですが月曜なので、実質コンテストの最終日です。貪欲がかなり良くなってきたのでビームサーチを書きたいなあという思いがあります。
一方で貪欲がまだ詰められそうな気もしています。もう少し貪欲を詰めてからビームサーチを書いてみるということをしたいと思います。まだ実戦でビームサーチがうまくいったことはありません。どこまでうまくいくかはわからないのですが、挑戦してみたいと思います。
さて、貪欲の方ですが、運び出す順番を変えたいと思っています。
たとえば233ターンかかっているseed11。最後4つになったときに同じ行のコンテナが残っています。最後4つになったときに別の行に搬出するコンテナになっていれば、ここから31ターンもかからないで終わることができそうです。
大クレーンが搬出するコンテナを各行同じ数になるように評価関数を変えたいと思います。たとえば（搬出する予定のコンテナ数（5）-搬出されたコンテナの数）×何倍みたいな数を評価関数に加えたいと思います。
seed6は233ターンから213ターンに短くなりました。さらに積極的に小クレーンが一番右端のコンテナを搬出するようにして、202ターンまで縮めることができました。
100テストケースで試します。よくなっているものもあれば、悪くなっているものもありました。
提出してみることにします。
あれ？下がってしまいました。少しだけ。100テストケースでは問題ありませんでしたが、提出したケースでは全て搬出できないものがあったようです。絶対スコアは6010937になっていました。相対スコアは14,615,063,459、201位でした。
うーん、ちょっと方針を考えます。
スコアが悪くなっていたseed0のビジュアライザを見ました。86ターン目でコンテナ7を搬出してもらいたいのですが、搬出せずに停滞したいました。
コードをなおすと、234ターンかかっていたものを201ターンまで縮めることができました。
100テストケースを試すとスコアが悪いものがあり平均は悪くなりましたが、メジアンが196でした。はっきりと良くなっているのがわかりました。提出します。
やったー！
ついに絶対スコアが1万を切り、9964になりました。相対スコアも16Gを超え、16,156,919,184、1054人中172位になりました。
ビジュアライザを見てスコアが悪いものを確認します。seed10の136ターン目でクレーン同士がお互いの進路をふさいで動けなくなっていました。この場合、動ける大クレーンに道を開けてもらいたいと思います。
無事、200ターンで終了するようになりました。100テストケースを試して提出します。全てがよくなったわけではありませんがこれからはこまめに提出をしたいと思います。結果はほんの少しよくなりました。
seed71ではコンテナ10を取るつもりが通り道に搬出できるコンテナ8があったのでつかんでしまうバグを修正しました。223ターンかかっていたのが201ターンになりました。
悪いのばかり見ていてもよくわからなくなってきたので、一番良いスコアのseedをみます。seed38ではスコア160が出ていました。これでもまだ無駄な動きを感じるので、スコア150くらいまではいけそうな気がします。そこまでがんばれば20Gにいけそうです。
相手とぶつからないようによけている箇所が無駄に感じます。
だんだん以前のAHCとの既視感を感じてきました。
そうだ、今ある合法手をその後貪欲でシミュレーション（プレイアウト）して一番スコアのよかったものを出力すればよいのではないだろうか、と。今の実行時間は32ms。制限時間の3秒に対してあまりにももったいない状況です。
コンテスト10日目にして考えることではないような気もしますが、コンテスト時間中に思い出せただけでも成長を感じます。
と思ったものの、どうすればよいかピンとこなかったので、バグを修正する作業を続けます。こつこつと修正して、100テストケースの平均が195.6ターンまで減りました。
提出をします。
絶対スコアが9612でした。9612÷50=192.24なので、そんなものなのかもしれません。相対スコアも提出前かの178位からほんの少しだけよくなりました。
そっかー、もうこのやり方ではスコアが上がらないのかなぁ。と思いつつ、小クレーンの目標の選び方を評価関数にします。
- まだ一時置き場に出されていないコンテナがある行は右詰めをする
- 右端にあるコンテナがあれば搬出する
- 距離が近い
100テストケースの平均は188.8ターンに下がりました。
提出をします。
絶対スコアは9362で平均は187.24。うん、そういうことですね。
相対スコアは提出前の177位、16,651,451,004から172位にあがりました。やっと17Gを超えました。ターンを5減少させると相対スコアが0.5G上がるイメージでしょうか。20Gにいくには平均173ターンくらいに減少させる必要がありそうです。
どうしよう？
小クレーンの数を増やすか。シミュレーションをするか。現在の最小スコアは159です。小クレーンを増やさなくてもたどりつけない数字ではないのかもしれません。悩みます。
19.小クレーンを増やす
考えた結果、小クレーンをもう1台増やすことにしました。現在の解法には手を加えず、3番目のsolverを書くことにします。
と思っていたものの、ちまちまとバグを修正ししていました。
順位表を見ると、トップは接戦のようです。
私の順位は1081人中186位、相対スコアは17,135,262,579です。
小クレーンを追加しようと思いますが気が重く、ちまちまとバグを修正します。絶対スコアは8866（平均177.32ターン）、相対スコアは17,998,702,068になりました。18G超えたい！
20.終わりに
コンテスト最終日、2024年5月27日の昼です。昨日は結局コードを書き直せずに疲れて眠ってしまいました。現在の順位は210位です。朝起きたときは相対スコアが18Gを超えていましたが画面を撮り忘れました。
小クレーンのコードは途中までは今後台数を増やせるよう書いていたつもりでしたが、最後はいろいろな継ぎ足しをしてしまったのでうまく書き直せませんでした。クレーンを2台しか使っていない人は自分以外にもいるのでしょうか。もっとこうすればよかったと後悔しそうですが、それでも自分なりにがんばったので、コンテスト終了後に参加した人たちの解法を聞くのがとても楽しみです。
今回のコンテストもとても楽しい時間を過ごすことができました。バグらせている時間が長かったけど、その先にクレーンがきっと良い動きをしてくれるはずと思って必死にがんばっていた時間はとても幸せな時間でした。
夢中になれるものがあるというのは本当にうれしくて、幸せなことだなあと思います。
100テストケースで一番スコアのよかったseed25のビジュアライザです。これを見るとやっぱりちゃんと小クレーンを増やさないといけなかったなあと思います。
今日の2024年5月27日（水）21時からはXでAHC033感想会スペースを開く予定です。お時間のある方はぜひお気軽にご参加ください。話したい方、聞きたい方、どちらも大歓迎です。
また、2024年5月29日20時からはAHCラジオもあります。こちらもぜひお楽しみに。
そして、ここまで長い文章を読んでいただきありがとうございました！これで参加記は終わりです。もし、今までヒューリスティック・コンテストには参加したことがないけれど、この参加記を読んで参加してみようと思ってくださった方がいればうれしいです。また、コンテストに参加していた皆様、お疲れさまでした。この後のシステムテストが気になるかと思いますが、ゆっくり休んでくださいね。と書いている自分自身は前回はシステムテストが気になって眠れなかった気がします。どうぞ無事システムテストが終わりますように。
おまけ：コンテスト残り時間10分くらいのときに見たら18Gを超えていました。
21.最終結果（2024年5月30日更新）
システムテストが終わりました。222位でした。2000テストケース全てACしていましたが、1ケースだけ全部運び出せずにスコア1000401のものがありました。それを除くと平均スコアは180.42でした。
ヒューリスティックのレーティングは19上がり、1675になりました。
20で紹介している公式のAHCラジオ（公式解説）は必見です。wataさんの解説を聞いて、あー、自分は違った方向に進んでしまったなあと思いました。復習をするために録画を見ながら、wataさんの言っていることを全然理解していない返事をしている自分の姿に見ていて恥ずかしくなりましたが、めげずにがんばりたいと思います。見てイライラしている方がいたらごめんなさい。
でもね、やっぱりあると良いですよね、解説放送が。そしてユーザ解説も充実しています。うれしい。次のコンテストが始まるまでにがんばって復習したいと思います。
