Day 103-Q5 — 最大空き長方形（Largest Empty Rectangle）

2026-07-26 赤色 Master / Phase 8+ ★★★★★★★★☆ 座標圧縮 + 候補境界列挙 O(N³)

問題

幅$W$、高さ$H$の長方形の土地に$N$個の障害物点（すべて内部、$0内部に含まない、辺が座標軸に平行な長方形（土地に収まる）の中で面積が最大のものを求めよ。境界線上に点が乗るのは許容する。

鍵となる事実は「最適な長方形の4辺は、必ず土地の境界か、いずれかの障害物点の座標に一致するように調整できる」という性質。これにより無限に存在する候補を有限個の候補に絞り込め、全探索が可能になる。

入力形式

W H N
x_1 y_1
:
x_N y_N

制約

$1 \le W,H \le 10^9$
$0 \le N \le 200$
$0
障害物点はすべて相異なる

入出力例

入力例1

10 10 5
3 3
3 7
7 3
7 7
5 5

出力例1

30

左辺$x=7$、右辺$x=10$（土地の右端）で作る幅$3$、高さ$10$の長方形には障害物点が1つも含まれず、面積$3\times10=30$が最大。

入力例2

5 5 0

出力例2

25

障害物点が1つもない場合、土地全体$5\times5=25$がそのまま答え。

概念図

入力例1: W=H=10、答え=30 (3,3) (3,7) (7,3) (7,7) (5,5) 最大長方形: x∈[7,10], y∈[0,10] 面積=3×10=30

ヒント（段階的開示）

ヒント1: 方向性
長方形の4辺の座標は連続値の範囲で無限に選べるように見えるが、ある辺を少しだけ動かしても途中に障害物点がなければ面積は変わらないか増える一方。動かせるだけ動かした「行き止まり」の位置だけを調べればよい。
ヒント2: アプローチ
最適な長方形の左辺・右辺の$x$座標は、必ず土地の境界（$0$または$W$）か障害物点の$x$座標のどちらかに一致させられる。左辺の候補集合$\{0\}\cup\{x_i\}$と右辺の候補集合$\{x_i\}\cup\{W\}$の組み合わせ（$O(N^2)$通り）それぞれについて、その縦帯の中に厳密に入っている障害物点の$y$座標を集めてソートし、隣り合う点の間の最大の隙間（$0$と$H$を番兵として含める）を求めれば、その帯での最大の高さが分かる。
ヒント3: 誘導（コード骨格） 
xs = sorted(set([0, W] + [p[0] for p in points]))
best = 0
for i in range(len(xs)):
    Lx = xs[i]
    for j in range(i + 1, len(xs)):
        Rx = xs[j]
        width = Rx - Lx
        ys = sorted(set([0, H] + [p[1] for p in points if Lx < p[0] < Rx]))
        for k in range(len(ys) - 1):
            height = ys[k+1] - ys[k]
            best = max(best, width * height)
print(best)

$N\le200$なら$O(N^3)$で十分高速に計算できる。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    w = int(data[idx]); idx += 1
    h = int(data[idx]); idx += 1
    n = int(data[idx]); idx += 1
    points = []
    for _ in range(n):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        points.append((x, y))

    xs = sorted(set([0, w] + [p[0] for p in points]))
    best = 0
    m = len(xs)
    for i in range(m):
        lx = xs[i]
        for j in range(i + 1, m):
            rx = xs[j]
            width = rx - lx
            if width * h <= best:
                # この時点でどうがんばってもbestを超えられないなら打ち切り
                continue
            ys_between = sorted(
                set([0, h] + [p[1] for p in points if lx < p[0] < rx])
            )
            for k in range(len(ys_between) - 1):
                height = ys_between[k + 1] - ys_between[k]
                area = width * height
                if area > best:
                    best = area

    print(best)


solve()
計算量: $O(N^3)$（$N^2$通りの帯 $\times$ 各帯での$O(N)$の高さ探索、$N\le200$を想定）。

Step-by-Step 解説

1なぜ座標を点の座標に限定できるのか
辺を障害物にぶつかるまでスライドさせても面積は減らないため、最適解は必ず「点の座標または土地の境界」の組み合わせで表現できる。
2左辺・右辺の候補を列挙
境界$\{0,W\}$と全障害物点の$x$座標を集めて重複を除きソート、$O(N^2)$通りの組み合わせを候補にする。
3縦帯の中での最大の高さ
帯の中に厳密に入っている点の$y$座標を集め、$0,H$を番兵に加えて隙間の最大値を求める。
4全帯を通じた最大面積の更新
「幅×その帯での最大の高さ」の最大値を全体の答えとする。

よくあるミス

ミス原因正しい書き方
境界上の点も「内部に含む」として除外してしまう「内部」と「境界」の区別を誤解帯の中の点を集める際は`Lx < p[0] < Rx`のように厳密な不等号を使う
左辺・右辺の候補に土地の境界（$0,W$）を含め忘れる障害物が少ない場合、境界自体が最適な辺になることがある候補集合を$\{0,W\}$と全点の$x$座標の和集合にする
$y$座標の番兵として$0,H$を入れ忘れる土地の端までの隙間を見逃す`ys_between`の集合に必ず$0$と$H$を含める
$O(N^4)$の実装にしてしまう4辺すべてを独立に全探索している左右の帯を固定した後は$y$座標の隙間だけで高さが決まるため実質$O(N^3)$で済む

次のステップ

  • 発展: 障害物が点ではなく矩形（使用済み領域）の場合への拡張（走査線 + セグメント木）
  • 発展: $N$が大きい場合（$N\le10^5$程度）の$O(N\log N)$アルゴリズムへの改良
  • 次回予告: （Master Levelローテーション継続、次回の出題テーマは実行時に選定）

自己評価

自分の回答

気づき・メモ