【AHC034】緑コーダーの競プロ参加記録 #24
今回はAtCoder Heuristic Contest 034です。
ヒューリスティックでは水コーダーですがタイトルそのままです。
結果は 451 位、パフォーマンスは水色の 1303 でした。
AHCに敷居の高さを感じている方に「こんなもんでこれくらいの順位なんだ」と知ってもらえれば幸いです。
ヒューリスティックコンテストに参加しよう！
「AHCはレートが下がらないので参加するだけ得！」
コンテストによってはサンプルコードが与えられることもあります。それをそのまま提出するだけで緑perfが出たりしますし、サンプルから1点でも改善すればperfに200くらい差が出たりもします。
アルゴリズム部門のレートはあまり関係ありません。コンテストによっては開催期間が2週間くらいあったりするので気軽に参加してみましょう。
問題概要
$${N \times N}$$の土地がある。
マス$${(i, j)}$$の高さは$${h_{i,j}}$$。
操作 A: 現在位置から土砂を$${d}$$だけダンプカーに載せる。現在位置の高さが$${d}$$減少する。コスト $${d}$$。
操作 B: 現在位置に土砂を$${d}$$だけダンプカーから降ろす。現在位置の高さが$${d}$$増加する。コスト $${d}$$。
操作 C: 上下左右に移動する。積載量$${d}$$に対してコスト $${100 + d}$$。
上手くダンプカーを操作して、土地を平坦化してね。
スコアはこんな感じです。
Step 1. グルグル移動する
どうすれば良い結果になるのか全くわかりません。
とにかく土地全体を平坦にすることだけを目指します。
とりあえず、機械的に全マス回ることにします。
ジグザグ移動でもよいですが、グルグルすることにしました。
現在位置$${(i, j)}$$について、$${h_{i,j} > 0}$$なら$${h_{i,j} = 0}$$になるように土砂を積み、$${h_{i,j} < 0}$$なら可能な限り土砂を降ろします。
片道だけだと$${h_{i,j} < 0}$$であるマスがいくつか残るので往復します。
（実は最後の1マスの穴が埋まっていません。）
スコア：2,956,668,022 点
提出コード
https://atcoder.jp/contests/ahc034/submissions/54635591
Step 2. 無駄に積まない
移動するとき、積載量に応じてコストが増えてしまうので、なるべく余計な土砂は載せないようにしたいです。
往路について、この先どれだけの深さの穴があるかを調べます。
つまり、$${k}$$番目に到達するマス$${(i, j)}$$について$${A_k = |\min(0, h_{i,j})|}$$として$${A}$$の累積和を後ろからとります。
現在位置より先にあるすべての穴について、現在の積載量分の土砂ですべての穴を埋められるなら、これ以上積載量を増やさないことにします。
これに加えて、どうせ往復するので最初の方で土砂を積んでも無駄になる可能性もあります。
よって、往路では$${t}$$ターン目以降から土砂を積み始めることにします。この$${t}$$は全探索して、最もスコアが良かったものを最終出力とします。
復路は Step 1 と同じです。
明らかに無駄にグルグルしているのですが、実装が間に合いませんでした。
スコア：3,796,719,095 点
提出コード
https://atcoder.jp/contests/ahc034/submissions/54642421
あとがき
短期コンは難しい 。
ではまた～。
