ABC 298 G — Strawberry War

考察

各最終pieceは部分長方形で、そのイチゴ数最小値は全部分長方形和の有限候補集合に含まれる。

採用する候補: 最小値候補列挙+長方形分割DP

下限aを固定すれば、m片へ切った最大piece和の最小値を長方形・片数DPで求め、max-minを評価できる。

棄却する候補: 全切断順を列挙

切断位置と順の分岐が指数的。

最後の一切りは水平または垂直で二長方形へ分かれるため、片数配分を列挙すればoptimal substructureが成立する。

2D prefix和で全長方形和候補aを列挙する。各aごとにdp[rect][m]を、m=1は和≥aなら和、m>1は全切線・片数分割のmax(dp1,dp2)最小として計算しdp[whole][T+1]-aを最小化する。

典型の発動条件

guillotine partition DP

発動条件: 長方形を直線切断で所定個数へ分割する。

最後の切断と片数配分で区間DPする。

最小値候補固定

発動条件: 目的がmax(piece)-min(piece)。

minを実現可能な部分長方形和に固定してmaxを最小化する。

問題固有の要素

H,W≤6なら高次多項式でも、実在するpiece和だけを下限候補にし状態の不可能条件で強く枝刈りできる。

別の問題へ持ち帰る視点: 小盤面最適分割は最後のcutと目的値固定を組み合わせる。

正当性

最後に使った切線を固定すると二つの長方形ができ、それぞれの内部の切り方は独立である。最小piece和の下限aを固定したDPでは、未切断pieceは和≥aの時だけ許し、切断では二部分の最適最大piece和のmaxを最小化する。切線と片数配分を全列挙するので全guillotine分割を覆い、逆に全遷移は実行可能な切り方を表す。最適解の最小piece和はどれかの長方形和なので、全長方形和aを試せばその解も候補に入り、求める最小max−minが得られる。

実装上の注意

  • T回切断はT+1片。rect面積<mを除外し、INF状態のmax加算を避ける。全体の苺数は最大36×10^16なので符号付き64 bitで持つ。

復習の核

  • 小盤面の全guillotine切断と比較し、T=0相当基底、全0、一cell大値、片数=面積を確認する。

計算量と制約

時間

O(R²(H+W)T²)、R=H(H+1)W(W+1)/4、下限候補R個×長方形/片数/最後の切線DP。

空間

O(RT+HW)、下限一つ分のDP。

制約との対応

公式制約の確認範囲: Time limit: 6 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H,W \leq 6; 1 \leq T \leq HW-1; 0 \leq s_{i,j} \leq 10^{16}; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Strawberry War の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間合成・領域分割DP

主題
  • 区間合成・領域分割DP: 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 区間合成・領域分割DP

    補助タグ: 有界全列挙・有限case分解 累積和・差分配列

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 区間合成・領域分割DP

    • 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題