概要

\(N \times N\) の掲示板に対して、高橋君が貼る \(A\) 個の長方形広告と、青木君が貼る \(B\) 個の長方形広告があります。このとき、「高橋君の広告の少なくとも1つ」と「青木君の広告の少なくとも1つ」の両方に覆われているマスの総数を求める問題です。

考察

掲示板のサイズ \(N\) は最大 500 であり、マスの総数は \(N^2 = 250,000\) です。この程度のサイズであれば、各マスについて「誰の広告が貼られているか」という情報をメモリ上に保持して直接カウントすることが可能です。

素朴なアプローチ

各広告について、指定された長方形の範囲 \((r_1, c_1)\) から \((r_2, c_2)\) までをループで回して「広告あり」とマークする方法が考えられます。 しかし、この方法では1つの広告が掲示板全体を覆う場合、1つの広告につき \(O(N^2)\) の計算量がかかります。広告の数は \(A+B \le 200\) なので、全体で \(O((A+B)N^2) \approx 5 \times 10^7\) となり、Pythonなどの言語では実行時間制限が厳しくなる可能性があります。

効率的な解決策：2次元いもす法

より効率的に長方形領域を加算するために、2次元いもす法（2次元階差配列）を利用します。 2次元いもす法を用いると、1つの長方形領域への加算を \(O(1)\) で行うことができます。すべての広告を処理した後に、2次元累積和を計算することで、各マスが何個の広告で覆われているかを \(O(N^2)\) で求めることができます。

アルゴリズム

1. グリッドの準備: 高橋君用のグリッド grid_T と青木君用のグリッド grid_A を用意します。サイズは境界外参照を防ぐため \((N+2) \times (N+2)\) とします。
2. 広告のプロット（いもす法）: 各広告 \((r_1, c_1, r_2, c_2)\) に対して、以下の4点に加減算を行います。
   • grid[r1][c1] += 1
   • grid[r1][c2+1] -= 1
   • grid[r2+1][c1] -= 1
   • grid[r2+1][c2+1] += 1
3. 累積和の計算: 各グリッドに対して、行方向、次に列方向の累積和をとることで、各マス \((r, c)\) がいくつの広告に覆われているかを復元します。
4. 重複マスのカウント: すべてのマス \((r, c)\) （\(1 \le r, c \le N\)）を走査し、grid_T[r][c] > 0 かつ grid_A[r][c] > 0 であるマスの数をカウントします。

計算量

• 時間計算量: \(O(N^2 + A + B)\)
  • 広告のプロットに \(O(A+B)\)、累積和の計算と集計に \(O(N^2)\) かかります。\(N=500\) のとき \(N^2 = 250,000\) なので、十分に高速です。
• 空間計算量: \(O(N^2)\)
  • \(N \times N\) のグリッドを数枚保持するためのメモリが必要です。

実装のポイント

• 1-based への対応: 問題文の座標は 1 から始まります。配列のサイズを \(N+2\) にしておくことで、座標をそのままインデックスとして扱いつつ、いもす法で使う r2+1 や c2+1 の境界外参照をスマートに防ぐことができます。

• 累積和の最適化: 行ごとの累積和をとった後に列ごとの累積和をとる処理は、2重ループで記述できます。提供されたコードでは、メモリ効率と速度を考慮して行ごとに加算を行っています。

  ソースコード

import sys

def solve():
    # Set recursion limit just in case
    sys.setrecursionlimit(2000)
    
    # Fast I/O: read all input at once and split by whitespace
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # Board size N, number of Takahashi's ads A, number of Aoki's ads B
    N = int(input_data[0])
    A = int(input_data[1])
    B = int(input_data[2])
    
    # grid_T and grid_A will store the 2D difference arrays for Takahashi and Aoki.
    # We use (N + 2) x (N + 2) to safely handle 1-based indexing and (r2+1, c2+1) boundaries.
    grid_T = [[0] * (N + 2) for _ in range(N + 2)]
    grid_A = [[0] * (N + 2) for _ in range(N + 2)]
    
    idx = 3
    # Process Takahashi's A ads and update the difference array
    for _ in range(A):
        if idx + 3 >= len(input_data):
            break
        r1, c1, r2, c2 = map(int, input_data[idx:idx+4])
        idx += 4
        
        # Standard 2D Imos/difference array update for a rectangle
        grid_T[r1][c1] += 1
        grid_T[r1][c2+1] -= 1
        grid_T[r2+1][c1] -= 1
        grid_T[r2+1][c2+1] += 1
        
    # Process Aoki's B ads and update the difference array
    for _ in range(B):
        if idx + 3 >= len(input_data):
            break
        r1, c1, r2, c2 = map(int, input_data[idx:idx+4])
        idx += 4
        
        # Standard 2D Imos/difference array update for a rectangle
        grid_A[r1][c1] += 1
        grid_A[r1][c2+1] -= 1
        grid_A[r2+1][c1] -= 1
        grid_A[r2+1][c2+1] += 1
        
    # Compute 2D prefix sums for grid_T to determine which cells are covered
    # Step 1: Row-wise prefix sum
    for r in range(1, N + 1):
        row = grid_T[r]
        for c in range(1, N + 1):
            row[c] += row[c-1]
    # Step 2: Column-wise prefix sum
    for r in range(1, N + 1):
        curr_row = grid_T[r]
        prev_row = grid_T[r-1]
        for c in range(1, N + 1):
            curr_row[c] += prev_row[c]
            
    # Compute 2D prefix sums for grid_A and simultaneously count overlapping cells
    # Step 1: Row-wise prefix sum for grid_A
    for r in range(1, N + 1):
        row = grid_A[r]
        for c in range(1, N + 1):
            row[c] += row[c-1]
    
    ans = 0
    # Step 2: Column-wise prefix sum for grid_A and check overlap with Takahashi's coverage
    for r in range(1, N + 1):
        curr_row_A = grid_A[r]
        prev_row_A = grid_A[r-1]
        row_T = grid_T[r]
        for c in range(1, N + 1):
            curr_row_A[c] += prev_row_A[c]
            # If the cell (r, c) is covered by at least one ad from both Takahashi and Aoki
            if curr_row_A[c] > 0 and row_T[c] > 0:
                ans += 1
    
    # Print the final count of overlapping squares
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。