AHC031

やったこと

縦に切った盤面を構築し、日ごとには横線のみを更新する
縦線の切り方は、 $d$ 日間動かさずに耐えられる範囲でなるべく細く切る
切った後の分け方は、なるべく細いところで入るだけ入れる
列ごとに、翌日と全く同じ位置で切れるなら切る（列のすべての切れ目がキープできる場合のみ）
縦線の集合を決めると貪欲で決める
- 左から順に貪欲に使うマスを決める（入るやつをなるべく大きく取る）
- その後右から順に「区切り線を前日と完全一致させられるなら一致させる」をする
縦線の集合の決め方は適当に焼きなまし
- 序盤は「区切り線を前日と完全一致させられるなら一致させる」を入れない
- 後半はスコアそのものを評価関数

やりたかったこと

たぶんこれをやると結構伸びる（実験した感じ、列ごとの要素数が多いものだと 2 倍ぐらい良くなりそう）と思ってたけど実装がむずすぎて 5 日ぐらいかかっても実装しきれなくて泣いてた *1 。

列を初日から順に、貸出先とその順列ブロックを決める
- 左右どちらかと同じ高さになるところに「切れ目」を設けて、各切れ目間に入る貸出先の集合（「ブロック」と呼ぶ）および左右のどの切れ目と対応するかのみを保持する
- 具体的な高さは決めない（上の情報からなるべく高さが低くなるように計算できる）
各長方形の高さは自由度を持たせておく
各日の中では、下から順にブロックを決める
- 列ごとにをしていい感じに決める
  - $\mathrm{DP}_{i}$ ：下から $i$ 個の貸出先まで決めたときの最適状態たち
  - 最適判定は、前日との共通切れ目の個数、（同じなら）動かせる自由度の大きさ、全体で必要な高さ、の辞書式順序で
  - 遷移は $\mathrm{DP}_{i}$ を求めるときは $0 \le j \lt i$ をすべて調べる。
探索の方法は
- 前日の自由度がある部分（ブロック内の入れ替え）を自由に動かすときに、可能な切断位置の集合を決めておく
- 今見ている列のうちまだ使っていないやつを自由に動かす
  - Combinations をすべて試せば簡単
  - ブロックごとの要素数が多い場合は最初の $100$ 個とかで適当に切っても良い
- 前日の該当部分のブロックの要素数が $a$ 個、当日分が $b$ 個であれば $2^{a+b}$ ぐらいの自由度があるのでそこそこ近いものができる
- bisect か尺取りで近いところをくっ付ける

感想

短冊はすぐ思いついたけどそこからの伸びが・・・
DP 実装仕切りたかった。

ビジュアライザ

今回はいつもに比べて公式の機能が少なかった気がする *2 。

長期コンは考察しやすいように自作するのが良さそう。

#AHC031
ビジュアライザはこんな感じにしてた。
前日と異なる線は左半分、翌日と異なる線は右半分が赤くなる。
灰色は不要部分。
長方形をクリックすると Information Box に表示されるいつものやつ。

動画は Seed 5 で 3 万切るぐらい https://t.co/t9EMhmTnao pic.twitter.com/BF6lP0BMIq
— きり (@kiri8128) April 1, 2024