概要

\(N \times M\) のサイズのグリッド（カード）において、指定された \(K\) 箇所のマスを穴（.）にし、それ以外のマスを穴なし（#）として出力する問題です。

考察

この問題を解くためのポイントは以下の3点です。

1. グリッドの初期化: 最初はすべてのマスに穴が開いていないため、まず \(N \times M\) の全マスを # で埋めた状態を作ります。
2. 座標の変換: 問題文ではマスの位置が \(1\) から始まる番号（1-indexed）で与えられますが、プログラム上の配列やリストは通常 \(0\) から始まる番号（0-indexed）で管理します。そのため、入力された \((R_i, C_i)\) を \((R_i - 1, C_i - 1)\) に変換して扱う必要があります。
3. 効率的な入出力: \(N, M\) が最大 \(1000\)、つまりマス目の総数が最大 \(10^6\) となるため、Pythonで大量のデータを扱う場合は、標準の input() や print() よりも高速な sys.stdin.read や sys.stdout.write を使用するのが望ましいです。

アルゴリズム

以下の手順で実装します。

1. \(N \times M\) の2次元リスト（grid）を作成し、すべての要素を '#' で初期化します。
2. \(K\) 回のループを回し、各ステップで与えられた座標 \((R_i, C_i)\) に対応する grid[R_i - 1][C_i - 1] を '.' に書き換えます。
3. 完成した grid の各行を文字列として結合し、順番に出力します。

計算量

• 時間計算量: \(O(NM + K)\)
  • グリッドの初期化に \(O(NM)\)、穴を開ける操作に \(O(K)\)、出力に \(O(NM)\) かかります。制約下では最大 \(10^6\) 程度の操作であり、制限時間内に十分間に合います。
• 空間計算量: \(O(NM)\)
  • \(N \times M\) のグリッドを保持するために必要なメモリ量です。

実装のポイント

• リスト内包表記: [['#'] * M for _ in range(N)] とすることで、効率的に2次元リストを生成できます。

• 高速な入出力:

  • sys.stdin.read().split() を使うことで、すべての入力を一括で取得し、空白や改行で区切られた単語のリストとして扱えます。

  • "".join(row) を使ってリストを一行の文字列にまとめてから出力することで、一文字ずつ出力するよりも大幅に高速化できます。

    ソースコード

import sys

def main():
    # 入力をすべて読み込み、空白で分割してイテレータに変換します
    # 大量の入力データを高速に処理するために sys.stdin.read().split() を使用します
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    
    # N: 行数, M: 列数, K: 穴の数
    try:
        N = int(next(it))
        M = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # N x M のグリッドを '#'（穴なし）で初期化します
    # Pythonのリスト内包表記を用いて効率的に作成します
    grid = [['#'] * M for _ in range(N)]
    
    # K 個の穴の位置 (Ri, Ci) を読み込み、グリッドを '.'（穴あり）に更新します
    # 座標は 1-indexed なので、0-indexed に変換するために 1 を引きます
    for _ in range(K):
        try:
            r = int(next(it))
            c = int(next(it))
            grid[r - 1][c - 1] = '.'
        except StopIteration:
            break
            
    # グリッドの各行を文字列に結合して出力します
    # 出力の高速化のため sys.stdout.write を使用します
    for row in grid:
        sys.stdout.write("".join(row) + "\n")

if __name__ == '__main__':
    main()

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