概要

\(N \times N\) の掲示板上で、高橋君の広告（複数の長方形）と青木君の広告（複数の長方形）の両方に覆われるマスの数を求める問題です。2次元いもす法を使って各マスの被覆状態を効率的に計算します。

考察

素朴なアプローチとその問題点

最も単純な方法は、高橋君の各広告と青木君の各広告のすべてのペア（最大 \(A \times B = 10000\) 組）について、重なる長方形を求め、覆われるマスを集合で管理する方法です。しかし、各長方形は最大 \(N^2 = 250000\) マスを覆う可能性があり、全体の計算量が大きくなりがちです。

重要な気づき

この問題では「高橋君の広告のどれか1つ以上に覆われているか」「青木君の広告のどれか1つ以上に覆われているか」が各マスについて分かれば十分です。つまり、各マスについて：

• 高橋君の広告に1回以上覆われている → フラグ ON
• 青木君の広告に1回以上覆われている → フラグ ON
• 両方 ON のマスを数える

この「長方形の領域に一括で値を加算し、最後に各マスの累積値を求める」処理は 2次元いもす法 で効率的に行えます。

アルゴリズム

2次元いもす法の仕組み

長方形 \((r_1, c_1)\) 〜 \((r_2, c_2)\) に \(+1\) を加算したいとき、\((N+2) \times (N+2)\) の配列に対して以下の4点を更新します：

• \(grid[r_1][c_1] += 1\)
• \(grid[r_1][c_2+1] -= 1\)
• \(grid[r_2+1][c_1] -= 1\)
• \(grid[r_2+1][c_2+1] += 1\)

すべての長方形についてこの操作を行った後、行方向・列方向に累積和を取ると、各マス \((r, c)\) の値がそのマスを覆う長方形の枚数になります。

\[grid[r][c] += grid[r-1][c] + grid[r][c-1] - grid[r-1][c-1]\]

手順

1. 高橋君の \(A\) 個の広告について、配列 grid_a に2次元いもす法で加算
2. 青木君の \(B\) 個の広告について、配列 grid_b に2次元いもす法で加算
3. 両方の配列について累積和を計算
4. 各マス \((r, c)\) について \(grid\_a[r][c] > 0\) かつ \(grid\_b[r][c] > 0\) なら重なりとしてカウント

具体例

例えば \(N=5\) で、高橋君の広告が \((1,1)\)〜\((3,3)\)、青木君の広告が \((2,2)\)〜\((4,4)\) の場合、累積和を取った後に \(grid\_a[r][c] > 0\) かつ \(grid\_b[r][c] > 0\) となるのは \((2,2)\)〜\((3,3)\) の \(4\) マスです。

計算量

• 時間計算量: \(O(N^2 + A + B)\)
  • いもす法の差分更新が \(O(A + B)\)、累積和の計算とカウントが \(O(N^2)\)
• 空間計算量: \(O(N^2)\)
  • 2つの \((N+2) \times (N+2)\) 配列を使用

実装のポイント

• 配列サイズを \((N+2) \times (N+2)\) にすることで、\(r_2+1\) や \(c_2+1\) が \(N+1\) になっても配列外アクセスを防げます
• 累積和の計算では、\(grid[r-1][c-1]\) を引く（包除原理）ことを忘れないようにしましょう
• grid_a[r][c] > 0 の判定で「1枚以上の広告に覆われているか」を確認しています。複数枚重なっていても関係なく、覆われているかどうかだけが重要です
• sys.stdin.read() でまとめて入力を読むことで、Python でも高速に動作します

ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    A = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1

    # 2D imos for Takahashi
    grid_a = [[0] * (N + 2) for _ in range(N + 2)]
    for _ in range(A):
        r1 = int(input_data[idx]); idx += 1
        c1 = int(input_data[idx]); idx += 1
        r2 = int(input_data[idx]); idx += 1
        c2 = int(input_data[idx]); idx += 1
        grid_a[r1][c1] += 1
        grid_a[r1][c2 + 1] -= 1
        grid_a[r2 + 1][c1] -= 1
        grid_a[r2 + 1][c2 + 1] += 1

    # 2D imos for Aoki
    grid_b = [[0] * (N + 2) for _ in range(N + 2)]
    for _ in range(B):
        r1 = int(input_data[idx]); idx += 1
        c1 = int(input_data[idx]); idx += 1
        r2 = int(input_data[idx]); idx += 1
        c2 = int(input_data[idx]); idx += 1
        grid_b[r1][c1] += 1
        grid_b[r1][c2 + 1] -= 1
        grid_b[r2 + 1][c1] -= 1
        grid_b[r2 + 1][c2 + 1] += 1

    # Compute prefix sums and count overlaps
    count = 0
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            grid_a[r][c] += grid_a[r - 1][c] + grid_a[r][c - 1] - grid_a[r - 1][c - 1]
            grid_b[r][c] += grid_b[r - 1][c] + grid_b[r][c - 1] - grid_b[r - 1][c - 1]
            if grid_a[r][c] > 0 and grid_b[r][c] > 0:
                count += 1

    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。