概要

\(N \times M\) の全てが # のグリッドを用意し、指定された \(K\) 個の座標だけ . に変えた最終状態を出力する問題です。

考察

最終的に必要なのは「穴を開ける」操作を \(K\) 回反映したあとの盤面なので、各指定 \((R_i, C_i)\) をそのまま . に更新していけば十分です。

素朴に「毎回グリッド全体を走査して穴位置を反映する」ような方法（例えば各操作ごとに \(N \times M\) を見直す）は、最悪で \(O(KNM)\) となり、\(N,M \le 1000\) では到底間に合いません。
この問題では 更新が必要なのは \(K\) 個のマスだけ という観察が重要で、各操作を \(O(1)\) で反映できれば合計 \(O(K)\) で済みます。

また、入出力が最大で \(N \times M \le 10^6\) 文字と大きめなので、Python では input() を繰り返すよりも高速な読み込み・書き出し（バッファIO）を使うと安全です。

アルゴリズム

1. 文字 # で埋めた \(N\) 行のグリッドを作る（各行は長さ \(M\)）。
2. \(K\) 個の座標 \((R_i, C_i)\) を読み取るたびに、
   • 1-indexed なので 0-indexed に直して \((R_i-1, C_i-1)\) とし、
   • 対応するマスを . に変更する。
3. グリッドを上から順に \(N\) 行出力する。

例：\(N=3, M=4\) で \((1,2)\) と \((3,4)\) に穴を開けるなら、初期状態

####
####
####

から更新して

#.##
####
###.

を出力します。

計算量

• 時間計算量: 初期化 \(O(NM)\) + 更新 \(O(K)\) + 出力 \(O(NM)\) なので全体で \(O(NM + K)\)
• 空間計算量: グリッド保持に \(O(NM)\)

実装のポイント

• 座標は入力が 1-indexed なので、配列アクセス前に必ず \(-1\) して 0-indexed に直します。

• Python では文字列は変更不可なので、各行を bytearray にすると grid[r][c] = ord('.') のように \(O(1)\) で書き換えられます。

• 入力は sys.stdin.buffer.read() でまとめて読み、整数パースを自前で行うと高速です（提出環境でのTLE対策）。

• 出力も sys.stdout.buffer.write() でまとめて行うと高速です。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
M = next_int()
K = next_int()

grid = [bytearray(b'#' * M) for _ in range(N)]

for _ in range(K):
    r = next_int() - 1
    c = next_int() - 1
    grid[r][c] = 46  # ord('.')

out = sys.stdout.buffer
for row in grid:
    out.write(row)
    out.write(b'\n')

この解説は gpt-5.2-high によって生成されました。