AHC034でフローなし、焼きなましなし、高速化不要(python ok)の比較的シンプルな貪欲解法で本番42位相当のスコア(7.9G)まで行けたので、解法をメモしておきます。アルゴ緑くらいの人なら十分理解できると思います。アルゴ緑、焼きなまし等のヒューリスティック専門知識は知らない、あるいはpython派なので焼きなましでは回数稼げない、という人でも40位くらいの高順位は十分狙えますよ、という話です。
問題文はこちら
大筋としては、まず全マスをなめて中央の縦の一直線に全部集めます。その後その中央の直線を一往復します。
全マスなめのルートはこんな感じです：
20x20全部描くのはめんどいので、はしょって描いています。最初と最後がちょっとイレギュラーな形ですが、それ以外は基本単純に全マスなめるだけです。'o'のところ以外は前半フェーズで全て高さゼロにしていきます。'o'のマスは、x:0..18, y:10 としています。
seed=0のGIFはこんな感じ：
最初、まず(0,0)->(1,0)に移動します。この後(0,0)->(0,1)->..->(0,9)と移動してその全てをゼロにしていくので、そのために必要な最小限の積荷になるよう、(1,0)で積むor降ろしておきます。具体的には、acc[0..9] = 「(0,0),(0,1),..,(0,9)の値の累積和」 としたとき、max(0,-min(acc))を積荷量とすればよいです。
この後(0,0)..(0,9)と移動します。各マスでは、高さが正ならそれを全部積む、負ならそのぶん降ろす、とします。つまり、高さゼロにします。負の時に降ろすぶんが足りなくならないよう、(1,0)で(必要なら)積み増ししてあります。
(0,0)..(0,9)をゼロにした後、(0,10)へ行きます。ここが最初の「調整ポイント」になります。次に (0,11)->(0,12)->..->(0,18)->(0,19)->(1,19)->(1,18)->..(1,11) と移動してその全てをゼロにしたい。そのため先ほどと同様、この経路の累積和を見て、必要最小限の積荷量にするよう(0,10)で積むor降ろします。
次に、また(1,10)で調整した後、(1,9)->(1,8)->..(1,0)->(2,0)->..->(2,9)を同様に処理します。最初に(1,0)でも調整の積み降ろしをしていますが、(1,0)はこの時にゼロになります。
以下同様に下辺まで行きます。最後が変な形なのは、終点を調整ポイントのライン上にするためです。
ここまでがフェーズ1。中央の調整ポイントの縦ライン以外は全て高さゼロになっています。ダンプは(18,10)にいます。フェーズ2ではこの縦ラインを一往復して全て高さゼロにします。
各マスから土を「どれだけ上(下)へ運び出すか、どれだけ上(下)から運び込むか」を決めます。上から(x=0から)考えていきます。h[0][10]>0 だとしましょう。x=0より下(x>0)のどこかのマスで、h[x'][10]<0 なマスへ土を運ぶ必要がありますが、そのようなx'の中でいちばん上(x小)なマスがいいはずです。同様に h[0][10]<0 なら、h[x'][10]>0 でいちばん上のマスから持ってくるのがいいはずです。
これを x=0,x=1,..x=17 と順にやっていくことによって、各マスから土を「どれだけ上(下)へ運び出すか、どれだけ上(下)から運び込むか」が決まります。これは言い換えると「上(下)に行く時、各マスでどれだけ積むか／降ろすか」、です。上に行く時はこれに従って積み降ろしします。下に行く時も同じようにやってもよいですが、下に行く時はとにかく全てゼロにすればいいのでそうします。
一往復で必ず全部埋められるのか？は気になるところですが、証明というほどではありませんが直感的に言うと、土を動かすのは必ず上方向(x=0方面)か下方向(x=19方面)のどちらかです。最初の上行きの時に埋められるものは全て埋めているので、残りの土は下行きのはず、つまり後半の下行きの時に残り全て動かせるはず、と言えます。…と考えてて「本当に大丈夫か？」と少し心配になってきましたが、まあシード1000個やって全てうまくいってるのでたぶん大丈夫でしょう。
説明は以上です。コードはこちらです。pythonで(余分なチェックやコメントやら全部入れて)206行。実行時間82msです。動作がわかるようにデバッグメッセージをstderrに出すようになってますが、これがうるさいという方は頭の"DBG = True"をFalseに変えると出さなくなります。