AHC034 参加記 - sankantsuのブログ

2024/06/16 15:00 - 19:00 に開催された AHC 034 に参加した。この記事では今回の参加について振り返る。

問題概要

N x N (N = 20) のグリッド上の領域があり、各マスの土の高さ h_ij が与えられている。土の高さは全て合計するとちょうど 0 になる。高さをならして平らにするような手順のうち、コストが最も低くなるものを求めたい。

結果

最終 135 位 (パフォーマンス 1918)

解法

トラックにあまりたくさん土を積みすぎると移動コストが高くなるので、一定量 K 積んだらそれらをいったん全て埋めに行く。積み荷が空になったら、また土を積みにいって、積み荷が K を超えたらそれらを全て埋めてという手順を繰り返す。各時点で拾いに行く場所 (または埋めに行く場所) は h > 0 (または h < 0) のうちBFS で最も近いマスを選ぶ。

なお、K を決め打ったときの1回の実行は 1ms 以下で終わるので、K の値を 80 から 280 まで動かして実行し、最も良いものを選ぶ。

提出コード

https://atcoder.jp/contests/ahc034/submissions/54640810

経過

問題を一通り読んだ感じでは今回は良さげな解法がさっぱり浮びません。ターン数重視なのか、それともターン数が増えても積荷の重さを低く抑えたほうが良いのかといったトレードオフがどのくらいのバランス感覚なのかというのが難しそうに思いました。

完全に平らにしなくても一応得点はつきそうな感じですが、さすがにストーリー設定からも高さ 0 に揃えるのは守ったほうが良さそうな気がしたので、とりあえず全マスの高さを 0 にできる簡単な実装を書いて観察してみることにします。

最も簡単そうな感じがしたのは、1周ジグザグに全マスを走査して、h > 0 のマスから余剰分を全部回収しておき、2周目は逆向きに回って h < 0 のマスを全部埋めていくというものです。若干バグらせつつも完成させ 16:05 に最初の提出。この時点でのスコアは 725,909,637 で 350 番台中盤。あまり筋の良い方針では無さそうです。

ナイーブな改善として思いついたのは、1周目の間に積荷を持っている状態で h < 0 のマスを通過したら、そのときついでに積荷を下ろしてしまうというもの。運ぶ途中の積荷の重さが軽くなるので良さそうな気がします。修正量はあまり多くないので 16:18 に提出できました。この時点でのスコアは 1,958,208,123 で倍以上良くなりましたが、まだ 300 番台です。

ちょっとまずいなと思いつつ、ビジュアライザでスコア的に良く無さそうな場所を観察してみると、やはり積荷が重くなりすぎるのが良くなさそうな感じがします。1000 以上載せた状態でしばらく走っていることもありました。

そこで、積荷の重さが一定以上溜まらないように制限して動かすことにします。そこで、積荷を K=100 だけ積んでは全部下ろすループに書きかえを行いました。また、毎回律儀にジグザグに走るのは明らかに無駄な動きが多いので、目的地はジグザグの経路順で前にあるものから決めるものの、次の目的地までは最短路で動くように書き変えて 17:14 時点で 5,021,333,480 です。この時点で 140 番ぐらいまで上がり、ようやく希望が見えてきた感じがしました。

さらに目的地自体も BFS で最も近い場所を探すように書きかえて 17:40 時点で 6,230,818,105 になり、さらに K を探索対象として複数パターン実行して良いものを選ぶことで 18:21 時点で 6,974,281,630 になりました。この時点では 2 桁順位まで上がっていましたが、結局ここから時間内にはスコアを伸ばせず 135 番でフィニッシュでした。