概要

\(N \times M\) のグリッド上で、指定された \(K\) 箇所に穴を開けた後のカードの状態を出力する問題です。

考察

この問題は、二次元配列を使ったシミュレーション問題です。

重要な気づき

1. 初期状態: すべてのマスが #（穴なし）
2. 操作: 指定された座標のマスを .（穴あり）に変更する
3. 座標の扱い: 問題文では1-indexed（1から始まる）だが、プログラムでは0-indexed（0から始まる）で扱うことが多い

なぜこの問題は単純に解けるか

• 各穴あけ操作は独立しており、順番は関係ない
• 同じ位置に穴が重複して指定されることはない（制約より）
• 配列の特定位置を書き換えるだけなので、各操作は \(O(1)\) で完了する

素朴なアプローチで十分高速に解けるため、特別な工夫は不要です。

アルゴリズム

1. \(N \times M\) の二次元配列を作成し、すべての要素を # で初期化する
2. \(K\) 回のループで、指定された座標 \((R_i, C_i)\) の位置を . に変更する
   • このとき、座標を0-indexedに変換する（\(R_i - 1\), \(C_i - 1\)）
3. 二次元配列を1行ずつ出力する

具体例

入力が以下の場合を考えます：

3 4 2
1 2
2 3

Step 1: 初期状態（\(3 \times 4\) のグリッド）

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

Step 2: \((1, 2)\) に穴を開ける → 配列では [0][1]

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

Step 3: \((2, 3)\) に穴を開ける → 配列では [1][2]

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

計算量

• 時間計算量: \(O(N \times M + K)\)
  • 配列の初期化に \(O(N \times M)\)
  • \(K\) 箇所の穴あけに \(O(K)\)
  • 出力に \(O(N \times M)\)
• 空間計算量: \(O(N \times M)\)
  • \(N \times M\) の二次元配列を保持するため

実装のポイント

1. 座標のインデックス変換: 問題文は1-indexed、Pythonのリストは0-indexedなので、R - 1 と C - 1 で変換する

2. リストの初期化: [['#'] * M for _ in range(N)] のようにリスト内包表記を使うと簡潔に書ける

   • 注意: [['#'] * M] * N と書くと、同じリストへの参照が複製されてしまいバグの原因になる

3. 出力時の結合: 各行は文字のリストなので、''.join(row) で文字列に結合して出力する

   ソースコード

# 入力を受け取る
N, M, K = map(int, input().split())

# すべてのマスが '#' のカードを作成
card = [['#'] * M for _ in range(N)]

# K箇所に穴を開ける
for _ in range(K):
    R, C = map(int, input().split())
    card[R - 1][C - 1] = '.'

# 結果を出力
for row in card:
    print(''.join(row))

---

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