参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針はまとめにまとめてあります。

問題概要

1 日目

ん、先週のトヨタコンに続きまた奥から詰めて取り出す系の問題？
めちゃくちゃ前回の知見が活きそうに見えるが... writer が asprova の方達なので普通に事故なのかな。
前回の解説放送まだ見てないので後で見ておこう。

さて、パッと思いついた方針としては、

迷路全体に木の形をした通路を張り巡らせる
その通路以外のセルを側根みたいな感じで通路から生えた細長い部屋の集合とみなす
各部屋はそれ自体も幅 1 の通路（ただし枝分かれは無い）となっていて、stack のノリで奥から詰めていく
- 種植え〜収穫の期間が長いものから奥に詰めていき、その手前には奥の期間に包含されるような期間の植物を置くことができる
大元の通路では栽培を行わず、各部屋を常に触れるようにしておく。

こんな感じか。

なんか最近卑屈になっていて、僕がパッと思いつく方針だと頑張って細部を詰めても 30 位くらいに落ち着くんだろうな...という気持ちになっている（特に通路では栽培を行わない、というあたりは改善の余地がありそうに思える）が、まぁ試してみないことにはなのでひとまず上の方針を実装してみることにする。

その前に栽培期間の分布みたいなものを押さえておきたいな。
式を見ると平均が 10 で、稀に 50~60 くらいのものが生えることもある、程度の感じに見える。了解。
K の生成方法は...？と思ってキョロキョロしてたが期間の総和が閾値超えた時点の作物の数が K になるのか。面白いな。

しかしあれだな、あまり長い期間のものがぽんぽん生えないのであれば、奥の期間に包含されるやつというよりは、D の値が同じで S の値が近い作物を同時にエイヤと部屋に敷き詰める感じになるのかもしれない。

あと、例えば S=1, D=T みたいな作物があったとして、それを倉庫の奥底に置くのはアリなのかナシなのかということを考えていた。
スコアを見ると、収穫した作物の最短栽培期間の和がスコアになるので、言い換えるとこれは各月 t=1, ..., T について、S_i <= t <= D_i の作物が埋まっているセルの数の和を取ったものということになる。
つまり、D_i = T の作物については t = S_i になった瞬間に倉庫の奥底に埋めるのが（その後そのセルで常にスコアが加点され続けることになるため）最善っぽい。OK
（後から気付いたけどビジュアライザの右側がこれだな...）

通路を構築する部分を書いている。色付きセルが通路で、出入口から DFS して葉から最初の分岐点までを切り落としたものなんだけど、う〜ん...ちょっと無駄が多いな...。
この通路は常に得点にならない部分になっちゃうのでできる限り削りたいのだけれど、まぁ方針が良さげだったら後で改善するか。

さて、通路と部屋さえ作ってしまえばあとは部屋ごとに独立して考えられるので、各部屋についてどの時刻に何を stack していくか考えていく。

動くものはできた。

部屋の中は結構良い感じの効率で回せてそうに見えるけど、提出したら 34M くらいだったので、やっぱり通路作る方針の筋が悪いのか...？でも通路ないと奥の方どうにもならんよねぇ。

部屋の作り方が悪いという話もある。

上図だと赤線に沿って縦長の部屋を作っているので部屋の入り口付近の効率が落ちてるけど、一番左の部屋は 82 から入るようにして通路沿いのセルはそれぞれ 1 マスの部屋とすればもっと効率良く回せるだろうし。

後は通路の末端をもう少し削ってそこも部屋にする、あたりか？

2 日目

木と部屋の作り方を少し賢くした。（壁沿いはできるだけ通路にしない、部屋は通路から BFS 的に広げていく、等）
手元で 36.5M。

通路と部屋については一旦これで多分良くて、次は効率の良い作物の割り当て方かな。
今は深い部屋から順に、最短収穫期間の長い順に置いていく貪欲みたいなことをしているので、ここもう少し改善できるはず。

あと気になってるのが、現時点での実装の手間に対して順位が体感より低い感じがするので、もっと単純なアイデアを見逃している可能性がある。

len=1: 4
len=2: 50
len=3: 172
len=4: 255
len=5: 314
len=6: 322
len=7: 354
len=8: 314
len=9: 320
len=10: 261
len=11: 230
len=12: 189
len=13: 139
len=14: 129
len=15: 90
len=16: 68
len=17: 12

使ってない作物どのくらいあるんだろう？と思って残った作物を最短収穫期間ごとに集計してみたら思ったより長い期間の作物はしっかり使われている、かつ短い期間の作物が意外と余っている。
通路の末端の方なら隙を見て植えられそうに見えるので、折を見てやる。

あるセルのある期間に対する収穫計画を決めたいとき、スコアが最大（タイブレークとして、使用する作物の数が最小）となる計画を DP で求めるようにした。38.2M。

部屋に詰めた後、通路にも置ける作物を置くようにした。38.6M。

さて、ここから 10% 伸ばせるようには見えないので、そろそろ固定の通路に頼らない別の方針考えるべきかな...。

いや、まだ通路の最適化が可能...？

3 日目

今は通路を作るとき壁からの距離が大きいセルほど低コストで移動できるようにしてダイクストラをしているが、一番外側の壁にはあまり通路を近づけたくない（通路を外に広げるほど通路自体のセル数が増えてしまう）ので、外側の壁に近い場合にペナルティを加えるようにした。38.9M。

無駄なジグザグを減らして通路セルの数をさらに減らした。39.1M。

通路にもっと作物を植えたいので、隙を突いて植えられるように部屋には最短収穫期間の長さが 3 以下の作物は植えないようにした。39.5M。

通路の方針まだ伸びるか...？
冷静に考えると固定の通路ナシでは無理ではという気もしなくもないか...？

どちらかというと部屋を固定にしてるのが良くないかも。

部屋の奥ほど最短収穫期間の長さにキツめの制約をかける（手前から x 番目の部屋には最短収穫期間が x + 2 以下の作物を植えない）ようにしたら急に 40.5M まで伸びた。オッ！？
なるほど奥には期間長めの作物植えるのが肝なのか？そう言われるとそれはそうな気がしてくる。

メモ: 今は長い部屋から順に全部埋めて次の部屋という DFS 的な流れだけど、奥から順繰りに埋めていく BFS 的な埋め方はどうだろうか？

4 日目

誘惑に負けてパラメータ等の調整をしてしまった。40.8M。

通路に作物を植える前の段階ではサイズが同じ 2 つの部屋はまるっと交換可能なので、通路に植えるのを阻害しないような部屋を交換してくるというのはある程度効きそうな気がする。実装重いけど...。

あと、通路に作物を植えるやつは葉から見て最初の分岐点に到達すると突如置けなくなる（下図参照）ので、最初の分岐点までが長い通路を優先して作物を植えてあげると嬉しそうな気がする。

あと、この通路にはこの作物を植える予定ですというのを決めてからその周辺の部屋を埋めた方が嬉しいことが起こりそうな気がする。

今日は疲れてるのでアイデア出して終わりにして良いか...？いいよ

5 日目

順位表を見るともうすぐ 44M が出そうになっている。暫定 16 位だけど伸びしろしかないなぁ。

この差のつき方はもう通路での収穫を頑張るしかないので、その方針で考えてみる。

考察の種に、今どんな感じでそれぞれのセルの収穫プランがどんな感じになってるのか、部屋ごとにスタックする形で表示してみる。
下に行くほど奥のセル。= はスコアが入っている生育期間、- はスコアが入らない生育期間。

賢そう。
そうそう、植えるときと違って収穫のタイミングは調整できないからちゃんと合わせてあげた方が良いんだよな。

うーん、やっぱり現状の「部屋の方はこんな計画にしました！通路さんこれに合わせて隙間時間に収穫してくださいね」よりも「通路側でここ、ここ、ここのタイミングで収穫するんで〜、部屋さんはそれに合わせて計画組んでくれます？」の方が筋が良さそうに見える。
通路側には複数の部屋が紐づいてるもんだから、部屋たちが違う要望をしてくるより通路側で決めて部屋に合わせてもらおう方が良さそう。

う〜〜ん、でも部屋側の計画を複数の部屋に強いると部屋での配置が厳しくなってくるか...？

ひとまず同じサイズの部屋の収穫プランを交換して通路の得点を最大化する山登りでも書くか。

できました。41.1M。

葉から見て最初の分岐点を通過してもまだ植えれていていいですね。

ちなみに今はこれランダムな 2 つの部屋の交換 → 通路に植える → 評価 → 通路の作物をリセットを 1 イテレーションとして 100 回くらいしかできてなくて、これの 50 倍回すとまだ 2% くらい伸びた。

伸びしろがあるのが分かったのは良いが、でも高速化はちょっと厳しいんだよな...。やっぱりランダムに山登りじゃなく、もう少し貪欲気味に行きたいところ。

6 日目

イテレーションの度に通路上の各セルに対して O(TK) の DP 走らせるのそりゃ重いよな〜と思って、自分より奥で収穫を行う月の集合をボトムアップで上に伝播させていくかたちで、各セルの収穫を行う月の数の和が最小になるようにしてみるとどうかな、と思った。
が、試してみるとちゃんと DP で計算するよりスコアちょっと落ちちゃった。
ちょっと評価指標としては雑すぎるか。

結局この後さらに 10 倍速くらいまで高速化して（何が高速化はちょっと厳しいんだよな...なんですか？）41.4M まで伸ばした。