トヨタ自動車プログラミングコンテスト2024#6（AtCoder Heuristic Contest 034）に参加し、AHC3回目にして想定以上にいい成績をとれたので記録を残しておきたいと思います。
焼きなまし、ビームサーチといったヒューリスティック向けのテクニックを一切学んでいないのですが、その割にはかなり健闘したと思っています。
結果
順位：74位
パフォーマンス：2153
最終スコアは7,562,888,852でした。（最終提出コード）
計算方法が違うとはいえ、3年近くやっているAlgorithmのレーティング（Highest: 1238, 6/20現在: 1134）をあっさり追い抜いてしまいました…
問題概要
縦横20マスの土地があり、各マスの高さが与えられる。土地全体で高さの総和は0。土を積み降ろしできるダンプカーが1台あるので、土の積み降ろしと移動によって土地を平らにしたい。
土の積み降ろしは土の量に応じたコスト、移動はダンプカーに積まれた土の量に応じたコストがかかる。可能な限り小さいコストで土地を平らにするような手順を求めよ。
経過
| 提出 | 開始からの経過時間 | スコア | 最終順位換算 |
|---|---|---|---|
| ① | 00:37:48 | 1,991,493,109 | 737位 |
| ② | 00:53:27 | 2,021,429,942 | 922位タイ |
| ③ | 01:24:25 | 2,486,767,225 | 683位タイ |
| ④ | 01:41:56 | 3,929,418,662 | 431位タイ |
| ⑦ | 02:48:18 | 4,757,491,082 | 362位 |
| ⑧ | 03:40:33 | 7,528,530,375 | 77位 |
| ⑨ | 03:47:51 | 7,562,888,852 | 74位 |
※⑤、⑥はバグがあり、超低スコア
ぱっと見での考察
- 高さが0にできていないマスがあるときのペナルティが大きいので、多少無理な動きをしても高さ0に持って行った方がよさそう
- 基本的には高いところから低いところへ土を運ぶだけでよく、過剰に土を積んだり掘ったりするのは意味がなさそう
- 移動回数と土を運ぶ量のバランス勝負になりそう？
- 一気に土を回収して運ぶ（移動コスト：大、移動回数：小）
- 少し回収しては少し降ろす（移動コスト：小、移動回数：大）
提出①
とりあえず土地全体をジグザグに走査してみる。高さが正のマスでは土を積み、高さが負のマスでは土を降ろすことですべてのマスの高さを0にする。負のマスで土が足りない場合は、その時点で持っている土すべてを降ろしておく。
全体を走査した後、0にできていないマスがあればルートを逆にたどり、土を降ろしていく。
提出するとスコアは1,991,493,109。この時点で約40分経過。
seed0, score=10,468,871 cost=475696
提出②
提出①では2週目ですべてのマスが高さ0になっても、左上のマスまで戻ることを優先している。ダンプカーが空であっても1マス移動するのにコストが100必要なため、seed0の場合はコストを2000近く損していることになる。すべてのマスが高さ0になった時点で終わるように修正。
提出するとスコアは2,021,429,942。この時点で約50分経過。
seed0, score=10,508,635 cost=473,896
提出③
土地の上の方に高さが負のマスが多いと2週目の序盤に無駄にジグザグすることになることが分かったので、縦にジグザグすることを試す。横方向と縦方向両方を試し、総コストが低かった方を採用させた。
提出するとスコアは2,486,767,225。この時点で約80分経過。
seed0, score=15,193,303 cost=327,776
提出④
1週目が終わった時点でかなり多くのマスが高さ0にできているにも関わらず、2週目も全マスをジグザグに走査するのは明らかに無駄。2週目は現在位置から最も近い高さ≠0のマスへ向かうように変更。1週目を縦横両方試す作戦は継続。
提出するとスコアは3,929,418,662。移動コストの定数100がバカにできないことを実感。この時点で約100分経過。
seed0, score=15,369,706 cost=324,014
seed0だと改善が実感しづらいが、2週目に入った時点で右1列目を走査せずに右上の青マス群に向かっていることが分かる
提出⑤、⑥
提出⑦の方針を実装したがバグっており、スコアが1/10以下に。
WAやTLEはなかったので、おそらく終了判定がバグっており、土地を平らにできていないのに終了してしまっていたと思われる。
提出⑦
提出④で「最も近いマスに向かう」を実装できたので、最初からこの方針で動かしてみる。
・高さが0でなく、現在位置から最も近いマスへ向かう
・ただし、土を積んでいない状態では高さが負のマスへは向かわない
この方針と横走査、縦走査の3つを実施し、最も良いものを採用。ここからコストではなくスコア${\dfrac{base}{cost+diff}}$の大小で比較している。コストを比較しているせいで方針比較が正しく行えずに⑤、⑥の低得点につながっていると思ってスコアでの比較に切り替えたが、多分根本原因ではなかった。
提出するとスコアは4,757,491,082。この時点で約170分経過。
seed0, score=18,709,285 cost=266,178
提出⑧
⑦ではほとんど何も考慮せず最寄りのマスに向かっているため、山になっているところに突っ込むと周辺の土をすべて回収してしまい、移動コストがかさんでいる様子が見られた。
そこで、⑦の方針に以下のルールを追加してみた。
・「最大積載量」を定め、ダンプカーに積まれた土が「最大積載量」を超えているときは高さが正のマスへは向かわない
1度ルートを求めるのに1,2msしかかかっていなかったため、「最大積載量」を0~5000の間で5刻みに変化させ、最もスコアが良くなるものを採用した。上限5000はかなり適当で、後から考えると明らかに大きすぎたと思う。
また、ここでようやく最初に土地全体を移動する方針を完全に捨てた。
提出するとスコアは7,528,530,375。一気にスコアが跳ね上がった。この時点で約220分経過（終了20分前）。
seed0, score=42,524,123 cost=117,110
提出⑨
提出⑧時点で残り20分であり、根本的な改善は難しいと考えた。しかし、提出⑧の実行時間が364msと、制限の2secまで余裕があることに目を付け、「最大積載量」を細かく刻むことに。「コードテスト」で実行時間とにらめっこしつつ、0~5000の間で2刻みとした。
提出するとスコアは7,562,888,852（微改善）。この時点で終了12分前だったため、これを最終提出とした。
seed0, score=42,827,657 cost=116,280
反省
今の実力でできることはほぼやった（むしろできすぎ）と思いつつ、もうちょっとできたかなぁと思うのが以下2点。
最寄りのマスの探索方法
提出⑧や⑨を見ると、終盤に高さ≠0のマス群がまばらに残ってしまって、それらの間の移動にコストがかかっていそう。コンテスト中も気づいてはいたが、改善できるロジックを思いつかず。
手元での実行環境の整備
複数のテストケースを一気に試すような実行方法を持っていなかったので、様々なテストケースを試してネックになっている部分を見つける、といった改善方法がとりにくかった。
これはすぐに取り組めそうなので、次回AHCまでには用意したいな…