ABC 347 F — Non-overlapping Squares

考察

重ならない二つの正方形は、上下か左右のどちらかに分かれている。この分離の向きに注目すると、三つの正方形の配置を少数の領域分割に整理できる。領域を先に決めてしまえば、その内部で最良の正方形を一つずつ独立に選べる。

一辺が MM の正方形の左上座標は O(N2)O(N^2) 通りある。三つの座標をそのまま列挙すると O(N6)O(N^6) 通りとなるうえ、重なりも判定しなければならない。そこで、座標の組を選ぶ代わりに、正方形同士を隔てる境界を選ぶことを考える。二つの正方形が行の範囲も列の範囲も共有していれば、共通のマスがある。従って非重複なら、少なくとも片方の方向に分離できる。

三つの場合も、どの正方形も横切らずに、一つと残り二つを分ける水平線または垂直線が必ず存在する。これは一組の分離だけからは言えないが、三組の分離方向を合わせると示せる。詳しい証明は正当性節で述べる。さらに、二つが入った側をもう一度分けると、分割の形は次の6種類になる。

  • 二本の水平線による横三段。
  • 二本の垂直線による縦三列。
  • 一本目と直交する線で片側だけを分けるT字の4回転。上・下・左・右のいずれか一領域が全幅または全高を占め、残りの側が二領域に分かれる。

各形について二つの切断位置を列挙すれば、分割の候補数は O(N2)O(N^2) に減る。ただし、毎回領域内の正方形を探し直しては遅い。次に必要なのは、各領域の最大値を定数時間で得る準備である。

二次元累積和から、左上が (r,c)(r,c) の M×MM\times M 正方形の総和 B[r,c]B[r,c] を求める。以下は元盤面の行・列とも1始まりとし、1≤r,c≤N−M+11\leq r,c\leq N-M+1 とする。例えば行 aa と行 a+1a+1 の間で切ると、上側へ完全に収まる条件は r+M−1≤ar+M-1\leq a、つまり r≤a−M+1r\leq a-M+1 である。左上座標が上側にあるだけでは足りず、正方形全体が収まる範囲へ変換する必要がある。

左上からの累積最大を U[r,c]=max⁡1≤u≤r, 1≤v≤cB[u,v]U[r,c]=\max_{1\leq u\leq r,\,1\leq v\leq c}B[u,v] とする。これは B[r,c]B[r,c]、U[r−1,c]U[r-1,c]、U[r,c−1]U[r,c-1] の最大を取って埋められる。他の三隅からも走査方向を変えて同じ表を作る。さらに、上・下・左・右の全幅または全高の領域に対する最大も用意する。いずれも O(N2)O(N^2) で前計算できる。候補が一つもない範囲の値は −∞-\infty とする。

T字のうち、上が全幅を占め、下を左右に分ける向きを具体的に考える。水平の切断位置を行 aa の直後、垂直の切断位置を列 bb の直後にすると、参照する左上座標は次のとおりである。表の範囲は、いずれも BB の有効な添字内に限る。

元盤面での領域完全に収まる正方形の左上座標
行 1…a1\ldots a の全幅r≤a−M+1r\leq a-M+1、列は任意
行 a+1…Na+1\ldots N、列 1…b1\ldots br≥a+1, c≤b−M+1r\geq a+1,\ c\leq b-M+1
行 a+1…Na+1\ldots N、列 b+1…Nb+1\ldots Nr≥a+1, c≥b+1r\geq a+1,\ c\geq b+1

上の全幅最大と、左下・右下からの累積最大を一つずつ参照すれば、この分割は O(1)O(1) で評価できる。他の三方向も回転して同様に求める。三領域のどれかが正方形を含めない切断は採用しない。

横三段では、中央の帯が上下の両方から制限されるため、隅からの累積最大だけでは評価できない。そこで、左上の行を固定したときの最大値を rowVal⁡[r]=max⁡cB[r,c]\operatorname{rowVal}[r]=\max_c B[r,c] として用意する。上の切断位置 aa を固定し、下の切断位置 bb を a+Ma+M から昇順に動かす。中央の帯は行 a+1…ba+1\ldots b なので、そこへ収まる左上の行は次の範囲である。

a+1≤r≤b−M+1a+1\leq r\leq b-M+1

各 aa の開始時に中央最大を −∞-\infty に戻し、各 bb で新たに入る rowVal⁡[b−M+1]\operatorname{rowVal}[b-M+1] との最大を取る。最初の b=a+Mb=a+M では行 a+1a+1 だけが入り、以降も追加分一行だけで更新できる。上段には r≤a−M+1r\leq a-M+1 の全幅最大、下段には r≥b+1r\geq b+1 の全幅最大を使う。M≤a≤N−2MM\leq a\leq N-2M、a+M≤b≤N−Ma+M\leq b\leq N-M の全組を調べれば、中央帯の処理も合計 O(N2)O(N^2) となる。N<3MN<3M なら横三段は存在しない。縦三列は行と列を入れ替え、列ごとの最大を伸ばして同じように評価する。

各分割では三領域が互いに交わらないため、領域内の最大を独立に選び、その和を候補にできる。6種類のすべての切断位置について最大を取ればよい。同じ配置が複数の分割に含まれても、最大値を求めるので問題ない。

典型の発動条件

幾何配置のseparator分類

少数の図形の位置を列挙しようとして候補が多すぎるときは、図形同士を分離する線で配置を分類できるかを考える。本問では三つの軸平行な正方形だから、一つと残り二つを分ける線の存在を証明できる。図形の個数や形を変えた問題でも同じ分割が使えるとは限らず、網羅性の証明が必要になる。

2D directional maximum前計算

左上座標で表した重みの表に対し、問い合わせる範囲が四隅からの長方形なら、四方向の累積最大を用意する。一般の長方形まで定数時間で求められるわけではない。本問の中央帯は切断位置を動かして最大を伸ばすことで、別に処理している。

問題固有の要素

「正方形を三つ選んでから重なりを調べる」代わりに、「重ならない三領域を決めてから一つずつ選ぶ」と、選択同士の依存を消せる。ただし、領域をまたぐ正方形を許すとこの独立性は崩れる。元盤面の切断位置から、正方形全体が収まる左上座標の範囲へ変換するところまでが一つの帰着である。

正当性

三つの正方形の各ペアは、行方向または列方向に分離できる。三ペアから分離方向を一つずつ選ぶと、少なくとも二ペアは同じ方向で、共通の正方形がある。その正方形の同じ側に残り二つがあれば、一つと残り二つを切り離せる。反対側にあれば三つの行区間または列区間がその方向に順に並ぶので、端の一つを切り離せる。従って必ず水平か垂直の線で1対2に分けられる。残る二つも分離すると、平行な二本による横三段・縦三列、または直交する線によるT字の四回転、計6種類で全配置を捕捉する。

各領域へ完全に収まる正方形だけを選ぶため、三つの領域最大の和は常に合法配置で達成できる。従って得られる値は真の最適値を超えない。一方、任意の最適配置は6種類のいずれかの分割に含まれる。その分割では、各正方形を領域内の最大のものへ置き換えても値が減らないため、評価値は真の最適値以上である。両方向から答えが一致する。T字は隅方向最大、三段は中央の行・列最大を逐次更新して評価するため、全切断位置を O(N2)O(N^2) で処理できる。

実装上の注意

  • 元盤面のマス境界と、表 BB の左上座標を区別する。切断の上・左では M−1M-1 を引き、下・右では切断の次の行・列から参照する。
  • 中央帯の最大は、外側の切断位置 aa を変えるたびに初期化する。前の aa の値を持ち越すと帯の外の候補が混ざる。
  • 正方形が収まらない領域を含む分割は候補から外す。番兵値を使うなら、加算時にオーバーフローさせない。
  • 正方形三つの総和は最大で 3M2×1093M^2\times10^9、累積和は最大で N2×109N^2\times10^9。いずれも64 bit整数で保持する。

復習の核

  • 位置の組合せが多いとき、図形同士を分ける境界を固定して、各領域の独立な最適化へ変えられないかを考える。
  • 分割形の列挙には、どの合法配置も含まれる証明を添える。本問は横三段・縦三列・T字4方向の6種類。
  • 隅からの累積最大で扱える範囲と、中央帯のように別の更新が必要な範囲を区別する。

計算量と制約

時間

O(N2)O(N^2)。二次元累積和、全正方形の和、方向別最大の前計算がそれぞれ O(N2)O(N^2)。四方向のT字切断、二方向の三段切断もそれぞれ O(N2)O(N^2) で評価できる。三段の中央最大は各外側切断ごとに初期化して伸ばし、各切断の組を定数時間で処理する。

空間

O(N2)O(N^2)。入力、累積和、正方形の和と方向別最大の表を保持する。

制約との対応

2≤N≤10002\leq N\leq1000、1≤M≤N/21\leq M\leq N/2、0≤Ai,j≤1090\leq A_{i,j}\leq10^9。O(N2)O(N^2) なら盤面のマス数に比例する処理で済む。2M≤N2M\leq N なので四隅のうち三つに正方形を置くことができ、少なくとも一つは合法配置がある。ただし三段・三列が収まらない場合もあるため、T字の4方向を省かない。実行時間制限は3秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Non-overlapping Squares の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 有界全列挙・有限case分解

    補助タグ: グリッド・多次元表の局所DP 累積和・差分配列

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

    学習の位置

    体系上の位置: 候補数を界して全列挙・有限case分解する

    • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

    先に読む単元:

    この解説で扱わないこと:

    • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題