AHC034 参加記 - physics0523's 精進ログ

誤った成功体験

A - Leveling with a Dump Truck

初手 : 「足りない」「余ってる」どちらにせよ、全マスを 2 回巡れば全マス 0 にはできるので、これを実装。マスの高さは過不足を調整できるだけ調整。

S字を描くように巡って 260 、渦を描くように巡って 384 。

渦を巻いたのは道中の重さの偏りを軽減するため。

しかし、この時点で 500 近い得点を出している方がいたのでいったん方針を棄却。

S字を描く 260

渦を描く 384

1 手目を終えて、おおよそ 1 時間くらい。

2手目 : 「最初に列で総和を揃え、その後行を合わせる」

列で総和を揃えれば低コストで行をなんとかできると予想。

最も左の列で総和を揃えて 519。

この時、改良として「2列ずつ見て、奇数列目で積んで偶数列目で積み下ろせばコストが減らせるのでは」と予想し取り入れるも 527 。

この時点で 700 台がいたのでこの方針も一旦棄却。

左端の列で行の総和を調整する方針 519

奇数列目で積んで偶数列目で積み下ろして調整する方針 527

2手目を終えて、おおよそ 1 時間 40 分くらい。

ここで、一度得点が 800 くらいになるとはどのようなことか考えてみる。

自分のスコアから逆算して、「おおよそコスト 13 万以内に抑えれば 800 」ということが分かる。

重大な事実として、全てのマスを巡るのに 4 万コストかかる。ここで、次の2択を迫られる。

全てのマスをおおよそ2回巡って残りコスト 5 万
全てのマスをおおよそ3回巡って残りコスト 1 万

そもそも $|h_i|$ が 25 くらいなのに後者はさすがにダメだろ… という直感で後者を棄却、前者の方向で進めていく。

残りコスト 5 万として、一歩当たりの積載量は 60 くらい。最初はこれをヒューリスティックに達成しようとしたが失敗して 30 分から 1 時間ほどロス。この時 LayCurse さんが 810 くらいを出していてまだ上があることを把握。この時点で 2 時間だったのでここから先心が折れないよう順位表情報をシャットアウト。

流石に積載量 60 をヒューリスティックするのは無理だと確信し、ひとまずコストの自明な下界を見積もろうとする。このとき、最初はマンハッタン距離でMCFしようとしたが、よくよく考えてみればマスの巡り方をそのままフローの辺に見立ててよいことに気づく。

図は、マスを綺麗に 2 巡した場合のダンプの動き方。

意識としては、砂を図中の矢印向きのコンベアに従って動かす感覚。適当に 2 マスをとって最短路を見てもらうとわかるが、 2 巡(本来欲しい 4 方位の半分くらいしか辺が無い)しかしてないのにほぼほぼ遠回りすることはないことが分かる。

このままフローを、流します(力技) 赤が 1 巡目、青が 2 巡目

土壌はいくら削りとってもいいようなものなので、一回「どこの砂をどこへ運ぶ」みたいなことは忘れて、とにかく各辺の時点でMCFのフロー分だけ砂を運べばいいことになる。この時点で MCF に対応する輸送が復元できることがわかり、 MCF の重みだけ見ると (2巡ぶんのコスト 80000) + 39000 とかが出てきた ( 最終コスト 119000 ) ので、これが 2 時間時点でのトップクラスの方針だと確信、実装して 777。

この時点でも実行時間は数msだったので、この解を結構な回数実行できることも分かる。

また、ウォークを取る(=MCF を流す)際に、なるべく「2 巡で使っていく辺が直交する」ように取ることを意識するようにする。こうすることで、無駄な辺を増やさずに効率的に輸送できる辺群が取れるという意識を念頭に?潜在意識に?置いて考察することに。

この時点で3時間食ってしまった。ここまではもたついてダメだったと反省。

しかし、これが神打開の始まりだった。ここからは本当に冴えていた。

全体を綺麗に2巡してMCF 777

ここで、先ほどのビジュアライザを見ると縦縞がけっこう見えることに気づく。なので、「1巡目か2巡目は綺麗に舐めなくてもいいのでは?」と気づく。

そこで、「1巡目か2巡目は1列飛ばしに舐める」という方針を取り入れる。これで 790 を受け取った。但しこの提出は本番提出がバグっていてスコアが不正確なので、方針だけ採用して正しく実装しなおした画像を載せる。

1列飛ばし 790 (正しく実装すれば874)

ここからは2巡目の歩数を削っていく。全体を巡るウォークを何通りか作っておき、ウォークのうち一番最後の歩みを消して求解を繰り返す。これで 899 。

1列飛ばしかつウォークの最後を削る 899

その後、「飛ばす段数は別に1段に限らなくてもいいので、2, 2.5, 3, 4段飛ばしというようにいくつかパターンを作ってから、時間が許す限り各パターンの後ろを削り続けることを試す」「1回目に k 段飛ばし・2回目に k 段飛ばしどちらも実装しているが、前者は全くといっていいほど採用されていないので切り捨てて後者のパターンに限定する」を追加して 918 に着地。