AHC023 解説

phspls

Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） のコンテスト中 & 後に考えたこと、あと提出での改善内容について書いています。
最終的には暫定テスト134位、システムテスト1,546,256,350点で140位相当の解法になります。

問題へのリンク

方針立て

問題文を読むと、植えた作物については必ず指定されたタイミングで収穫しないといけないので、奥の方に植えたものも取り出せるようにする必要があります。
それなら一番奥に植えた作物の「植えたタイミング」「収穫するタイミング」を基準に考えれば良さそうです。
例えばですが、$${H = 1, W = 5}$$, 水路なしの場合に作物を植えるような時を考えるとわかりやすいですが、

  1. 一番奥の区画に$${S_i}$$カ月目に作物$${i}$$を植え、$${D_i}$$ヶ月目に収穫する場合、その手前には$${S_i}$$ヶ月以降かつ$${D_i}$$ヶ月以前にしか植えて収穫することしかできない($${=}$$一番奥から1つ手前の区画では、植える〜収穫するタイミングで$${S_i}$$や$${D_i}$$を跨いではいけない)

  2. 1の条件を満たすように、一番奥から1つ手前の区画で$${S_i \le S_j, D_j \le D_i}$$となるように$${S_j}$$ヶ月目で作物を植え、$${D_j}$$ヶ月目で収穫する場合、さらに1つ手前の区画では$${S_j}$$ヶ月目以降に植え、$${D_j}$$ヶ月目以前に収穫しないといけない

  3. 以降同じ

です。

ただ上の考え方をそのまま全体に適用すると、$${H \times W = 400}$$なので、一番奥に植える作物は$${S_i = 1, D_i = 100}$$とかぐらいになりそうです。
そして(具体的には入力生成方法に書いてありますが)テストケースを色々試してみるとわかる通り、生成される作物の$${S_i, D_i}$$には偏りがあります。まず$${S_i = 1, D_i = 100}$$なんてデータはできませんし、それでもこのままこの考えを適用しようとするなら手前の方に植えられるものがなくなり、無駄が多くなります。

なので

  • $${H = 1, W = 5}$$の例みたいに、小さい範囲でなら考えられそう。

  • 実際は$${H = W = 20}$$なので、上記の小さい範囲を作るならそれらを複数作ることになる

  • 上記の小さい範囲たちの管理をうまくやったとして、小さい範囲たちはいずれも必ず出入口につながっていることを担保する必要がある

な感じで考えたところ、

  • 出入り口から作物を植えない道を生やす。小さい範囲がその道につながっていれば、それは(植える際にも収穫の際にも出入口までの道に妨げるものはないので)出入口につながっているのと同じ

  • 小さな範囲たちは必ず道につながっているようにする。逆に言えば道に辺でつながっている箇所をそれぞれ個別の小さな範囲の起点にする

  • 道に接していない区画については、小さな範囲の起点それぞれからBFSで最初にたどり着いた小さな範囲に属することにする

とするのが良さそうだとなりました。

道の生やし方については「道から一番遠い区画のマンハッタン距離が$${X}$$以下にする、$${X}$$については水路の混み入り具合で変わりそうなので、$${X}$$をランダムにしてスコアが良さそうなものを選ぶ」としました。

それぞれの小さな範囲についてどういう順番に作物を植えるか、そもそもどの小さな範囲にどの作物を割り当てるかは考えるのが複雑になりそうなので、とりあえず上記実装ができた上で、適当に前から順番に作物を割り当てて後で改善していこうという気持ちでやっていきました。

改善フェーズ

方針立てのところを基本にして、それから改善した点について書いていきます。

■$${S_i = 2}$$のものを全て$${S_i=1}$$として扱う

$${S_i = 2}$$のものについては、その作物を植えるつもりなら2ヶ月目に植えるメリットがありません。むしろデメリットのみです。

  • 2ヶ月目に植えるメリットは1ヶ月目に収穫できるものがあって、その収穫で空いた区画があるような場合です。そして今回の制約では最速でも収穫できるのは2ヶ月目です。

  • 2ヶ月目に植えるデメリットですが、方針立てのところに記載した「一番奥に植えたものを基準にする」の話になります。$${S_i = 1, D_i = 3, S_j = 2, D_j = 4}$$の2つの作物$${i, j}$$を植えたいと考えているとします。

    • $${S_j = 2}$$のままだと$${S_i = 1, D_i = 3}$$より作物$${i}$$より奥に植えられません。そして$${D_j = 4}$$なので作物$${i}$$を収穫できなくなるため、手前にも植えられません。

    • $${S_j = 2 \rightarrow 1}$$にしてやると、作物$${j}$$を作物$${i}$$より奥に植えることができます。

■道についても植えられる作物は植える

とりあえず道に何も植えない前提で解を作り、作り終えた後で道に植えられる範囲で植えます。道に接している小さな範囲で使う、植える / 収穫するタイミングに干渉しないように気をつけながら実装します。

■植える / 収穫する タイミングが同じものは極力同じ小さな範囲に植える

単純な話で、区画にはなるべく作物を植え続けた方がスコアは上がるので、それを達成するために小さな範囲では植える〜収穫するタイミングが等しい方が無駄がなくて良いです。

■$${S_i}$$の値を与えられたものより小さくした方が良い場合もある

任意の小さな範囲について、以下のような場合にメリットがあります。$${S_i}$$をそのままにした左より、小さくした右の方がより作物を植えられるようになります。
最終的には破棄した方法なのですが、一旦解を作り、そこからランダムに$${S_i}$$を1小さくしてスコアが良くなるだけ良くする山登りもできます。


最終解法

seed0の結果のgifを載せます。