概要

流れ星はすべて左上方向（対角線方向）に移動するため、同じ対角線上の「区間被覆問題」に帰着できる。各対角線ごとに、すべての区間を刺す最小の点集合を貪欲法で求める。

考察

重要な観察：流れ星は対角線上を移動する

\(k\) 番目の流れ星は時刻 \(t\) に \((R_k - t, C_k - t)\) にいます。行番号と列番号が同時に \(1\) ずつ減るため、差 \(R_k - C_k\) は常に一定です。つまり、各流れ星は \(R - C = \) 定数の対角線上のみを移動します。

異なる対角線上の流れ星は互いに干渉しないため、各対角線ごとに独立に考えればよいです。

対角線上での区間への変換

対角線 \(d = R_k - C_k\) 上で、流れ星 \(k\) が通過する行番号の範囲を求めます。

• 存在条件：\(R_k - t \geq 1\) かつ \(C_k - t \geq 1\)、つまり \(t \leq \min(R_k, C_k) - 1\)
• 通過する行の最小値：\(R_k - (\min(R_k, C_k) - 1) = \max(1,\ d+1)\)
• 通過する行の最大値：\(R_k\)（時刻 \(0\) の位置）

したがって、対角線 \(d\) 上で流れ星 \(k\) は行番号の区間 \([\max(1, d+1),\ R_k]\) を通過します。

区間刺し問題への帰着

カメラを \((r, c)\) に設置すると、同じ対角線 \(r - c = d\) 上で行番号の区間に \(r\) が含まれる流れ星をすべて撮影できます。

これは「与えられた区間すべてを少なくとも1つの点で刺すのに必要な最小点数」という最小点被覆問題（Interval Point Cover）に帰着されます。

アルゴリズム

各対角線について、古典的な貪欲法を適用します：

1. 流れ星を対角線 \(d = R_k - C_k\) ごとにグループ分けする
2. 各対角線内で、区間 \([L_k, R_k]\)（\(L_k = \max(1, d+1)\)）を右端 \(R_k\) の昇順にソートする
3. 区間を順に見ていき、まだカメラで撮影されていない流れ星に出会ったら、その区間の右端にカメラを設置する（右端に置くことで、後続の区間もできるだけ多くカバーできる）

具体例：対角線 \(d = 0\) に区間 \([1, 3]\), \([2, 5]\), \([4, 6]\) がある場合 - \([1, 3]\)：未カバー → 行 \(3\) にカメラ設置 - \([2, 5]\)：行 \(3\) がこの区間に含まれる → カバー済み - \([4, 6]\)：行 \(3\) はこの区間に含まれない → 行 \(6\) にカメラ設置 - → 計 2 台

計算量

• 時間計算量: \(O(N \log N)\)（各流れ星をグループ分けし、対角線ごとにソート。ソートの合計が \(O(N \log N)\)）
• 空間計算量: \(O(N)\)（流れ星の情報を保持する辞書）

実装のポイント

• \(H, W\) が最大 \(10^9\) と非常に大きいが、対角線の値 \(d = R_k - C_k\) で辞書にグループ分けすれば、座標圧縮は不要

• 区間の右端でソートし、last_placed（最後にカメラを置いた行番号）を管理するだけで貪欲法が実装できる

• 初期位置が同じ流れ星はないと保証されているが、同じ対角線上に複数の流れ星が存在しうることに注意

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    N = int(input_data[idx]); idx += 1
    
    # Each meteor k starts at (R_k, C_k) and moves to (R_k-t, C_k-t) for t=0,1,...,min(R_k,C_k)-1
    # The path of meteor k is all cells (R_k-t, C_k-t) where the diagonal is R_k - C_k = constant
    # and the position along that diagonal ranges from min(R_k, C_k) steps.
    # 
    # Specifically, on diagonal d = R_k - C_k, the meteor occupies cells where:
    #   if d >= 0: row goes from d+1 to R_k (i.e., col goes from 1 to C_k)
    #   if d < 0:  col goes from -d+1 to C_k (i.e., row goes from 1 to R_k)
    # 
    # We can parameterize by the diagonal d = R - C.
    # On a given diagonal, a meteor starting at (R_k, C_k) covers positions with
    #   row from (max(1, d+1)) to R_k  if d>=0, equivalently col from 1 to C_k
    #   row from 1 to R_k if d<0, equivalently col from (1-d) to C_k... 
    # 
    # Let me think in terms of a parameter along the diagonal. Let's use row number as the parameter.
    # Meteor k on diagonal d = R_k - C_k occupies rows from max(1, d+1) up to R_k.
    # Wait: the meteor goes from (R_k, C_k) towards (1,1) direction.
    # At time t, it's at (R_k - t, C_k - t). This exists while R_k - t >= 1 and C_k - t >= 1.
    # So t can go from 0 to min(R_k, C_k) - 1.
    # The rows visited are R_k, R_k-1, ..., R_k - (min(R_k,C_k)-1).
    # R_k - (min(R_k,C_k)-1) = R_k - min(R_k,C_k) + 1
    #   if R_k <= C_k: = 1
    #   if R_k > C_k: = R_k - C_k + 1 = d + 1
    # So the interval of rows is [max(1, d+1), R_k].
    # 
    # A camera at cell (r, c) with r - c = d on the same diagonal captures any meteor whose
    # row-interval contains r.
    # 
    # Problem reduces to: for each diagonal d, we have a set of intervals [L_k, R_k] on that diagonal.
    # We need to find minimum number of points to stab all intervals. This is a classic greedy:
    # sort by right endpoint, greedily pick the rightmost point of each unstabbed interval.
    
    # Group meteors by diagonal
    diagonals = defaultdict(list)
    
    for i in range(N):
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        d = R - C
        # Interval of rows: [max(1, d+1), R]
        L = max(1, d + 1)
        # The interval is [L, R] on this diagonal
        diagonals[d].append((R, L))  # store (right_end, left_end)
    
    total_cameras = 0
    
    for d, intervals in diagonals.items():
        # Classic interval point cover: sort by right endpoint
        intervals.sort()  # sort by R (right endpoint), then by L
        last_placed = -1
        for right_end, left_end in intervals:
            if last_placed < left_end:
                # Need to place a camera at right_end (greedy: as far right as possible)
                last_placed = right_end
                total_cameras += 1
    
    print(total_cameras)

solve()

---

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