概要

\(H \times W\) の台紙に対して、\(R \times C\) の形状を持つスタンプを計 \(N\) 回押した後の、最終的な台紙の状態を求める問題です。スタンプの # の部分は台紙を # に塗り替え、スタンプが台紙からはみ出す場合はその部分を無視します。

考察

素朴なシミュレーションとその課題

最も単純な方法は、スタンプを 1 回押すごとに、スタンプの全マス（\(R \times C\)）をループで確認し、台紙の対応するマスを更新することです。 この場合、全体の計算量は \(O(N \times R \times C)\) となります。 制約を当てはめると \(1000 \times 100 \times 100 = 10^7\) となり、Pythonのようなインタプリタ言語では、二重ループ内の処理が重なると実行時間制限（TLE）に間に合わない可能性があります。

ビット演算による高速化

この問題は、台紙の各行を「ビット列（2進数）」として扱うことで高速化できます。 - 台紙の 1 行を 1 つの整数として管理します。 - スタンプの各行もあらかじめビット列に変換しておきます。 - スタンプを押す操作を、ビット演算の OR（論理和） で行います。

ビット演算を用いると、横方向の \(C\) マス分の更新を一度の演算で処理できるため、計算量を \(O(N \times R)\) に削減でき、十分に高速に動作します。

アルゴリズム

1. スタンプの準備: スタンプの各行 \(S_i\) について、# を 1、. を 0 と見なし、整数（ビット列）に変換します。このとき、1列目が最下位ビット（LSB）になるように反転させておくと、後のシフト操作が直感的になります。
2. 台紙の管理: 台紙の各行の状態を保持する長さ \(H\) の配列 paper_bits を用意し、初期値はすべて 0 とします。
3. スタンプを押す操作: \(N\) 回の各操作 \((r_k, c_k)\) について以下を行います。
   • スタンプの各行 \(dr \in [0, R-1]\) について、台紙の行インデックス \(r_k + dr\) が台紙の範囲内（\(1\) 以上 \(H\) 以下）か判定します。
   • 範囲内であれば、スタンプの行ビット列を \(c_k - 1\) だけシフトさせ、台紙の行ビット列と OR 演算を行います。
     • \(c_k - 1 \geq 0\) なら左シフト（<<）
     • \(c_k - 1 < 0\) なら右シフト（>>）
4. 出力: 各行のビット列を 2 進数文字列に変換し、1 を # に、0 を . に置換して出力します。

計算量

• 時間計算量: \(O(RC + NR + HW)\)
  • スタンプの変換に \(O(RC)\)、スタンプを \(N\) 回押す操作に \(O(NR)\)、最終的な出力の生成に \(O(HW)\) かかります。
  • Pythonの多倍長整数によるビット演算は非常に高速であるため、実効速度は非常に速いです。
• 空間計算量: \(O(H + RC)\) または \(O(HW)\)
  • 台紙を行ごとの数値で持つ場合は \(O(H)\) ですが、最終的な出力文字列を構築する際に \(O(HW)\) のメモリを使用します。

実装のポイント

• 座標のオフセット: 問題文は 1-indexed ですが、プログラム内での配列操作に合わせて適切に調整する必要があります。

• はみ出し処理: \(r_k\) や \(c_k\) が負の値や \(H, W\) を超える値になる可能性があるため、max(0, 1 - rk) などの境界チェックを行い、不要なループやエラーを防ぎます。

• ビット列の復元: bin(val)[2:] で得られる文字列は上位ビットが左に来るため、1列目を左側に表示するには文字列を反転させる、あるいは zfill で幅を揃えるなどの処理が必要です。

  ソースコード

import sys

def solve():
    # Read all input at once for speed
    # The input size is roughly 10^6 characters for the stamp, plus integers for N, r_k, c_k.
    # Total memory usage will be well within the limits.
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Paper dimensions
    H = int(input_data[0])
    W = int(input_data[1])
    
    # Stamp dimensions
    R = int(input_data[2])
    C = int(input_data[3])
    
    # Preprocess the stamp into a list of bitsets (integers)
    # For each row, the 1st column is the 0-th bit (LSB).
    stamp_bits = []
    for i in range(R):
        s = input_data[4 + i]
        # Optimized bitset creation: replace '#' with '1' and '.' with '0',
        # then reverse to make the first column the LSB.
        b = int(s.replace('#', '1').replace('.', '0')[::-1], 2)
        stamp_bits.append(b)
        
    # Number of stamp applications
    N_idx = 4 + R
    N = int(input_data[N_idx])
    
    # paper_bits[1...H] stores the bitset for each row of the paper.
    # Initially, all cells are '.' (represented as 0).
    paper_bits = [0] * (H + 1)
    
    current_idx = N_idx + 1
    for _ in range(N):
        rk = int(input_data[current_idx])
        ck = int(input_data[current_idx + 1])
        current_idx += 2
        
        # Horizontal shift based on the stamp's column position
        shift = ck - 1
        # If the stamp is completely outside the horizontal bounds of the paper, skip it.
        if shift >= W or shift <= -C:
            continue
        
        # Determine which rows of the stamp (dr) overlap with the paper rows [1, H].
        # The paper row index is rk + dr, so we need 1 <= rk + dr <= H.
        start_dr = max(0, 1 - rk)
        end_dr = min(R, H + 1 - rk)
        
        # Apply the stamp row by row using bitwise OR operations.
        if shift >= 0:
            for dr in range(start_dr, end_dr):
                paper_bits[rk + dr] |= (stamp_bits[dr] << shift)
        else:
            s_abs = -shift
            for dr in range(start_dr, end_dr):
                paper_bits[rk + dr] |= (stamp_bits[dr] >> s_abs)
    
    # Final output generation
    mask = (1 << W) - 1
    output = []
    for i in range(1, H + 1):
        # Mask the row value to only include bits within the paper's width W.
        row_val = paper_bits[i] & mask
        
        # Convert the integer bitset back to '#' and '.' characters.
        # bin(row_val)[2:] gives the binary string, zfill(W) ensures it has length W,
        # and [::-1] ensures bit 0 (the 1st column) is at the start of the string.
        s_bin = bin(row_val)[2:].zfill(W)[::-1]
        output.append(s_bin.replace('1', '#').replace('0', '.'))
    
    # Print all rows joined by newlines.
    sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

---

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