第10回 Asprova プログラミングコンテスト（AHC023）参加記

48 位．

方針

大まかな方針：

通路を決める（図の赤線）
細長い部屋を作る（図の青線）
各部屋ごとに，配置する作物を貪欲に決める

通路・部屋の決定

以下のような山登り法を実施

通路にも部屋にも属さないマスが存在するまで以下を繰り返す
- いずれかの部屋を破壊して，その部屋を作り直す(伸ばせるだけ伸ばす)
  - もとの部屋のサイズより大きければそれを採用
- たまに，通路のマスを増やしたり減らしたりする（ただし通路が連結になるように増減させる）

作物の決定

各部屋ごとに，配置する作物を区間 DP で決めていった．

$dp \lbrack C \rbrack \lbrack L\rbrack \lbrack R\rbrack=$ 「 $L$ 日目から $R$ 日目まで，サイズが $C$ の部屋に配置できる作物のスコアの合計の最大値」

としたとき，以下のような漸化式が成り立つ．

$(S,D)=(L,R)$ となる残っている作物の個数を $M$ とすると

$C \leq M$ のとき $dp\lbrack C \rbrack \lbrack L\rbrack \lbrack R\rbrack=C(R-L+1)$
$C\gt M$ のとき $\displaystyle dp\lbrack C \rbrack \lbrack L\rbrack \lbrack R\rbrack=M(R-L+1)+ \max_{L\leq mid\lt R}(dp\lbrack C-M \rbrack \lbrack L\rbrack \lbrack mid\rbrack+dp\lbrack C-M \rbrack \lbrack mid+1\rbrack \lbrack R\rbrack)$

これに加えて， $(S,D)=(L+1,R)$ であるような作物を $L$ 日目に植えるようにした遷移も加えるとスコアが結構上がった（4.5 M くらい）．すなわち， $(S,D)=(L+1,R)$ となる残っている作物の個数を $M'$ とすると

$\displaystyle dp\lbrack C \rbrack \lbrack L\rbrack \lbrack R\rbrack=M(R-L+1) + M'(R-L) + \max_{L\leq mid\lt R}(dp\lbrack C-M-M' \rbrack \lbrack L\rbrack \lbrack mid\rbrack+dp\lbrack C-M-M' \rbrack \lbrack mid+1\rbrack \lbrack R\rbrack)$

みたいな遷移も追加した．計算量がやばくて，部屋ごとに DP テーブルを再計算する必要があるので，全体で $O(T^3 HW)$ かかってしまう．python だと無理そうだったので途中から c++ に書き換えた．DP の復元がめんどい．

感想

40.7 M くらいで頭打ちになってしまってそれ以降ほとんど何もできなかったのが残念．
ほとんどアルゴで殴ってしまってヒューリっぽいことができなかったのが残念．
上位陣は焼いていてすごい．こんなの焼けるんですね～（焼いている解法ツイート流れてきたけど何言ってるのかさっぱりだった）