概要

この問題は、H行W列の台紙にR行C列のスタンプをN回押すとき、最終的な台紙の状態を出力する問題です。スタンプは一部が台紙外にはみ出す場合があり、その部分は無視されます。

考察

問題を解く上で重要な観察点は以下の通りです： - スタンプを押す位置は負の値や台紙の範囲外になることがある - スタンプの各マスが台紙内に収まるかどうかをチェックする必要がある - 各スタンプ操作で、スタンプの「#」部分に対応する台紙のマスを「#」に更新する - 既に「#」になっているマスはそのまま保持する（重ね押ししても問題ない）

素朴なアプローチとして、各スタンプ操作ごとにスタンプ全体を走査し、対応する台紙の位置を更新する方法が考えられます。制約条件（H, W ≤ 1000, R, C ≤ 100, N ≤ 1000）から、最悪計算量はO(N×R×C) = 1000×100×100 = 10^7回程度となり、十分実行可能です。

アルゴリズム

1. H行W列の台紙をすべて「.」で初期化
2. N回のスタンプ操作を順に処理：
   • 各操作で、スタンプの左上位置(r_i, c_i)を受け取る
   • スタンプの各マス(dr, dc)について：
     • 対応する台紙の位置：行 = r_i - 1 + dr、列 = c_i - 1 + dc
     • この位置が台紙の範囲内(0 ≤ 行 < H, 0 ≤ 列 < W)かつ、スタンプの該当マスが「#」ならば、台紙の該当マスを「#」に更新
3. 最終的な台紙の状態を出力

計算量

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

実装のポイント

• スタンプの位置は1-indexedで与えられるので、0-indexedに変換する必要がある（r_i - 1, c_i - 1）

• 二重ループでスタンプの全マスを走査するが、範囲外チェックを忘れない

• スタンプが「#」のマスのみを処理することで効率化

• 既に「#」のマスを再度「#」にしても問題ない（上書きしても結果は同じ）

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    idx = 0
    H, W = map(int, data[idx].split())
    idx += 1
    R, C = map(int, data[idx].split())
    idx += 1
    stamp = []
    for _ in range(R):
        stamp.append(data[idx].strip())
        idx += 1
    N = int(data[idx])
    idx += 1
    operations = []
    for _ in range(N):
        r, c = map(int, data[idx].split())
        idx += 1
        operations.append((r, c))
    
    grid = [['.'] * W for _ in range(H)]
    
    for op in operations:
        r0, c0 = op
        for dr in range(R):
            r_pos = r0 - 1 + dr
            if r_pos < 0 or r_pos >= H:
                continue
            for dc in range(C):
                c_pos = c0 - 1 + dc
                if c_pos < 0 or c_pos >= W:
                    continue
                if stamp[dr][dc] == '#':
                    grid[r_pos][c_pos] = '#'
                    
    for i in range(H):
        print(''.join(grid[i]))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。