概要

\(H \times W\) の台紙に対して、同じ形の \(R \times C\) スタンプを \(N\) 回押したとき、最終的に # になっているマスを求めて出力する問題です。

考察

重要な気づき

• スタンプを押す操作は「対応するマスを # にする（OR を取る）」操作です。すでに # でも変化しません。
• スタンプの一部が台紙からはみ出しても、台紙内に入っている部分だけを反映すればよいです（範囲クリッピングが必要）。

素朴解がつらい理由

素朴には、各スタンプ操作ごとにスタンプの全マスを走査して

• # なら台紙に反映

とすると、計算量は最大で \(O(NRC)\) です。制約最大で \(1000 \times 100 \times 100 = 10^7\) 回程度なので言語によっては通ることもありますが、Python だと境界チェックや文字列操作が重なりやすく、余裕が小さくなります。

解決方針（ビット集合で高速化）

このコードでは、台紙の各行を「ビット列」として整数で持つことで高速化しています。

• 1 行を長さ \(W\) のビット列（# を 1、. を 0）として表す
• スタンプの各行も同様にビット列化する
• スタンプを押す操作は、該当行に対して
  board[row] |= (stamp_row_bits << shift)（または右シフト）
  という「ビット OR」と「シフト」だけで処理できる

これにより、\(C\) 個のマスを 1 つずつ更新する代わりに、整数演算 1 回でまとめて更新できます。

アルゴリズム

1. スタンプを行ごとにビット化

   • ./# を 0/1 に変換し、各行を 2 進数として int にする。
   • 実装では「左端の列を下位ビットにする」ために文字列を反転 [::-1] しています。
     これにより、列方向のずれは単純にシフトで表現できます。

2. 台紙も各行を整数（ビット列）で持つ

   • board[i] は台紙の \(i\) 行目（0-index）のビット表現。
   • まだ何も押していないので最初は全て 0。

3. 各スタンプ押しを処理

   • 入力の \((r, c)\) は 1-index なので、top=r-1, left=c-1 として 0-index 化。
   • はみ出しを考慮して、実際に重なるスタンプ行の範囲を
     • i_start（スタンプ側の開始行）
     • i_end（スタンプ側の終了行、半開区間） で求めます（クリッピング）。
   • 列方向のはみ出しはシフトで処理します：
     • left >= 0 なら stamp_bits[i] << left
     • left < 0 なら stamp_bits[i] >> (-left)
   • 台紙幅 \(W\) を超えるビットが立つのを防ぐため、mask=(1<<W)-1 で 常に & mask します。
   • 最後に board[top+i] |= shifted_bits で反映します。

4. 出力

   • 各行の整数を format(row, f"0{W}b") で \(W\) 桁の 2 進文字列にし、
   • ビットの並びを元の列順に戻すため [::-1] を行い、
   • 0/1 を ./# に変換して出力します。

計算量

• 時間計算量: \(O(NR)\)（各スタンプにつき、重なる行数ぶんのビット演算）
  • 厳密には Python の多倍長整数の演算コストが絡みますが、\(W \le 1000\) なので十分小さく、実用上高速です。
• 空間計算量: \(O(H)\)（台紙を行ごとの整数で保持）＋スタンプ \(O(R)\)

実装のポイント

• 座標のクリッピングが最重要です。top が負（上にはみ出す）、top+R が \(H\) を超える（下にはみ出す）などを、i_start, i_end で正しく切り詰めています。

• 列方向のはみ出しは、left が負なら右シフトで自然に処理できます（ただしシフト後に 0 になる場合があるので軽く条件分岐しています）。

• mask = (1<<W)-1 を使い、& mask で 台紙外（\(W\) 列より右）のビットを必ず落とすのが安全です。

• 入出力は sys.stdin.buffer.read() と split()、bytes.maketrans を使って高速化しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    H = int(next(it))
    W = int(next(it))
    R = int(next(it))
    C = int(next(it))

    tr_in = bytes.maketrans(b".#", b"01")
    stamp_bits = []
    for _ in range(R):
        s = next(it)
        stamp_bits.append(int(s[::-1].translate(tr_in), 2))

    N = int(next(it))

    board = [0] * H
    mask = (1 << W) - 1

    for _ in range(N):
        r = int(next(it))
        c = int(next(it))
        top = r - 1
        left = c - 1

        # Quick reject if no overlap
        if top >= H or top <= -R or left >= W or left <= -C:
            continue

        i_start = 0 if top >= 0 else -top
        i_end = R if H - top >= R else H - top
        if i_start >= i_end:
            continue

        if left >= 0:
            shift = left
            for i in range(i_start, i_end):
                b = stamp_bits[i]
                if b:
                    board[top + i] |= (b << shift) & mask
        else:
            s = -left
            for i in range(i_start, i_end):
                b = stamp_bits[i]
                if b:
                    shifted = b >> s
                    if shifted:
                        board[top + i] |= shifted & mask

    tr_out = str.maketrans("01", ".#")
    out_lines = []
    fmt = f"0{W}b"
    for row in board:
        out_lines.append(format(row, fmt)[::-1].translate(tr_out))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。