概要

\(H \times W\) の台紙に、\(R \times C\) のスタンプを \(N\) 回押したあとの台紙の最終状態を求める問題です。スタンプがはみ出す場合は台紙内の部分だけが刻印されます。

考察

問題の整理

台紙は最初すべて . で、スタンプの # の部分が台紙に転写されます。同じマスに複数回スタンプが押されても # のままなので、各マスについて「一度でも # が押されたかどうか」だけが重要です。

素朴なアプローチ

最も素朴な方法は、各スタンプ押しに対してスタンプの全 \(R \times C\) マスを走査し、# のマスを台紙に反映することです。これだと最悪 \(N \times R \times C = 1000 \times 100 \times 100 = 10^7\) 回の処理が必要ですが、十分高速です。

重要な気づき

• スタンプの # の位置だけを事前に列挙しておけば、. のマスをスキップできるため無駄な処理を省けます。
• スタンプの位置が台紙外にはみ出す場合があるため、各 # マスが台紙の範囲内に収まるかチェックが必要です。
• 座標が 1-indexed で与えられ、さらに 0 以下や \(H\), \(W\) より大きい値もあり得るため、座標変換と範囲チェックを正しく行う必要があります。

アルゴリズム

1. スタンプの前処理: スタンプの中で # であるマスの相対座標 \((sr, sc)\) をすべてリストに格納します。

2. 各スタンプ押しの処理: \(j\) 回目のスタンプ押しでは、スタンプ左上が台紙の \((r_j, c_j)\)（1-indexed）に置かれます。0-indexed に変換して \((r_0, c_0) = (r_j - 1, c_j - 1)\) とします。

3. 有効範囲の計算: スタンプの行方向・列方向について、台紙内に収まる範囲を計算します。

   • 行: \(sr\_start = \max(0, -r_0)\), \(sr\_end = \min(R, H - r_0)\)
   • 列: \(sc\_start = \max(0, -c_0)\), \(sc\_end = \min(C, W - c_0)\)

4. 刻印: 前処理で求めた各 # 位置 \((sr, sc)\) が有効範囲内であれば、台紙の \((r_0 + sr, c_0 + sc)\) を # に変更します。

5. 出力: 全スタンプ押し後の台紙を行ごとに出力します。

具体例

例えば台紙が \(5 \times 5\)、スタンプが以下の \(2 \times 2\) だとします：

#.
.#

スタンプの # 位置は \((0,0)\) と \((1,1)\) です。左上を \((2, 3)\)（1-indexed）に合わせると、0-indexed で \((1, 2)\) なので、台紙の \((1, 2)\) と \((2, 3)\) が # になります。

計算量

• 時間計算量: \(O(N \times K)\)（\(K\) はスタンプ中の # の個数、最大 \(R \times C = 10^4\)）
  • 最悪 \(O(N \times R \times C) = O(10^7)\) で十分高速
• 空間計算量: \(O(H \times W + R \times C)\)（台紙とスタンプの格納）

実装のポイント

• bytearray の利用: 台紙を bytearray で管理することで、2次元配列より高速にアクセスできます。paper[pr * W + pc] = 35 で '#'（ASCIIコード 35）を直接書き込みます。

• 1-indexed → 0-indexed の変換: 入力の座標は 1-indexed なので、r0 = rj - 1, c0 = cj - 1 と変換する必要があります。

• 範囲外チェック: スタンプ位置が大きく台紙外にずれている場合（有効範囲が空の場合）にも、個別に範囲チェックするフォールバック処理があります（コード中の if sr_start >= sr_end or sc_start >= sc_end の分岐）。

• 高速入力: sys.stdin.buffer.read() でまとめて読み込み、split() でトークン分割することで I/O を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    
    H = int(tokens[idx]); idx += 1
    W = int(tokens[idx]); idx += 1
    R = int(tokens[idx]); idx += 1
    C = int(tokens[idx]); idx += 1
    
    stamp = []
    for i in range(R):
        stamp.append(tokens[idx]); idx += 1
    
    N = int(tokens[idx]); idx += 1
    
    # Use a flat array for the paper
    paper = bytearray(b'.' * (H * W))
    
    # Precompute stamp '#' positions
    stamp_positions = []
    for sr in range(R):
        for sc in range(C):
            if stamp[sr][sc] == '#':
                stamp_positions.append((sr, sc))
    
    for _ in range(N):
        rj = int(tokens[idx]); idx += 1
        cj = int(tokens[idx]); idx += 1
        
        # rj, cj are 1-indexed positions for the top-left of the stamp
        # Convert to 0-indexed
        r0 = rj - 1
        c0 = cj - 1
        
        # Determine the valid range of stamp rows/cols that fall within the paper
        sr_start = max(0, -r0)
        sr_end = min(R, H - r0)
        sc_start = max(0, -c0)
        sc_end = min(C, W - c0)
        
        if sr_start >= sr_end or sc_start >= sc_end:
            # Check if any stamp_positions fall in range
            for sr, sc in stamp_positions:
                pr = r0 + sr
                pc = c0 + sc
                if 0 <= pr < H and 0 <= pc < W:
                    paper[pr * W + pc] = 35  # '#'
            continue
        
        for sr, sc in stamp_positions:
            if sr_start <= sr < sr_end and sc_start <= sc < sc_end:
                paper[(r0 + sr) * W + (c0 + sc)] = 35  # '#'
    
    # Build output
    out = []
    for i in range(H):
        out.append(paper[i * W:(i + 1) * W].decode())
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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