概要

与えられたスタンプを指定された位置に複数回押した結果、台紙がどのようになるかをシミュレーションする問題です。

考察

この問題では、\(N\) 回のスタンプ操作を一つずつシミュレーションすることで答えを求めることができます。

ポイントとなるのは以下の通りです：

• スタンプは常に同じ形状であり、各マスが # か . かによって台紙に印がつくかどうかが決まります。
• スタンプの左上を \((r_i, c_i)\) に合わせて押すので、スタンプの各マスが台紙のどの位置に対応するかを計算できます。
• ただし、スタンプが台紙からはみ出す場合があるため、範囲外参照を防ぐ必要があります。
• また、一度 # になったマスは再度 # になっても変化しないので、単純に上書きすればよいです。

素朴な方法として、毎回のスタンプについて、その全マスを見て台紙に反映するというアプローチがありますが、これは十分高速です。なぜなら、スタンプのサイズは最大でも \(100 \times 100\) で、操作回数も最大で1000回なので、全体で最大でも \(100 \times 100 \times 1000 = 10^7\) 程度の計算になり、時間内に間に合います。

アルゴリズム

1. 入力を読み込みます。特に座標は1-indexedで与えられるので、内部処理では0-indexedに変換します。
2. 台紙を表す二次元配列 paper を . で初期化します。
3. 各スタンプ押しについて、以下のように処理を行います：
   • スタンプの各 # のマス \((dr, dc)\) に対して、それが台紙上のどの位置 \((r_{\text{paper}}, c_{\text{paper}})\) に対応するかを計算します： $\( r_{\text{paper}} = r_{\text{top}} + dr,\quad c_{\text{paper}} = c_{\text{left}} + dc \)$
   • その位置が台紙の範囲内（\(0 \leq r_{\text{paper}} < H\) かつ \(0 \leq c_{\text{paper}} < W\)）であれば、そのマスを # にします。
4. 最終的な台紙の状態を出力します。

計算量

• 時間計算量: \(O(N \cdot R \cdot C)\)
• 空間計算量: \(O(H \cdot W + R \cdot C)\)

※ 台紙のサイズ \(H \times W\)、スタンプのサイズ \(R \times C\)、スタンプ押し回数 \(N\) に対してです。

実装のポイント

• 座標系が1-indexedで入力されるので、内部で0-indexedに変換すること。
• スタンプの各 # のマスだけを処理することで効率よくシミュレーションできる。
• 範囲外アクセスを防ぐために、更新前に \(0 \leq r < H\) かつ \(0 \leq c < W\) であることを確認する。

## ソースコード

```python
H, W = map(int, input().split())
R, C = map(int, input().split())
stamp = [input() for _ in range(R)]
N = int(input())
stamps = [tuple(map(int, input().split())) for _ in range(N)]

# 1-indexed -> 0-indexed
stamps = [(r - 1, c - 1) for r, c in stamps]

# 台紙の初期化
paper = [['.' for _ in range(W)] for _ in range(H)]

# スタンプを押す処理
for r_top, c_left in stamps:
    for dr in range(R):
        for dc in range(C):
            if stamp[dr][dc] == '#':
                r_paper = r_top + dr
                c_paper = c_left + dc
                if 0 <= r_paper < H and 0 <= c_paper < W:
                    paper[r_paper][c_paper] = '#'

# 出力
for row in paper:
    print(''.join(row))

---

この解説は qwen3-coder-480b によって生成されました。