概要

\(H \times W\) のマス目にある電球を、指定されたマスとその上下左右を反転する操作を \(Q\) 回行い、最終状態を求める問題です。各操作で影響を受けるのは最大 \(5\) マスだけなので、素直にその \(5\) マスだけを反転すれば十分です。

考察

重要な観察

まず、電球の状態は「反転」だけで変化することに注目します。反転は XOR（排他的論理和）そのものなので、

• 同じマスを \(2\) 回反転すると元に戻る
• 反転の順番は結果に影響しない

という性質があります。したがって「操作を順番にシミュレートする」ことと「各マスが何回反転されたかを数えて、偶奇だけ見る」ことは同じ結果になります。

素朴なアプローチとその問題点

一見ありそうな失敗パターンは次の \(2\) つです。

(1) 毎回グリッド全体を走査してしまう

「操作のたびに全マスを見て、対象かどうか判定して反転する」という実装をすると、\(O(QHW)\) = 最大 \(10^5 \times 10^6 = 10^{11}\) となり全く間に合いません。

しかし実際には、\(1\) 回の操作で状態が変わるのは $\((r, c),\ (r, c-1),\ (r, c+1),\ (r-1, c),\ (r+1, c)\)\( の**最大 \)5\( マスだけ**です。ここだけを直接書き換えれば、\)1\( 回の操作は \)O(1)$ で処理できます。

(2) 文字列を毎回作り直してしまう

Python で S[i] = S[i][:j] + ('1' if ... ) + S[i][j+1:] のように文字列を組み替えると、\(1\) 回あたり \(O(W)\) のコピーが発生します。\(W\) は最大 \(10^6\) になり得るので、\(Q = 10^5\) 回では致命的です。Python の文字列はイミュータブル（変更不可）なので、可変なデータ構造を使う必要があります。

解決方針

• グリッドを 1 次元の可変バイト列（bytearray） として保持する。
• マス \((i, j)\)（\(1\)-indexed）は添字 \(p = (i-1) \times W + (j-1)\) に対応させる。
• 反転は grid[p] ^= 1 の \(1\) 命令で行える。

ここで少し技巧的なのは、bytearray に文字 '0', '1' をそのまま格納する点です。ASCII コードは '0' = \(48 = \texttt{0b110000}\)、'1' = \(49 = \texttt{0b110001}\) なので、最下位ビットだけが違います。よって ^= 1 するだけで '0' ↔ '1' が入れ替わり、数値と文字の変換が一切不要になります。出力時もそのままバイト列として書き出せます。

アルゴリズム

1. 入力を sys.stdin.buffer.read().split() で一括読み込みする。
2. \(S_1, \dots, S_H\) を連結して長さ \(HW\) の bytearray を作る（これがグリッド）。
3. 各操作 \((R_k, C_k)\) について、\(p = (R_k-1)W + (C_k-1)\) とし、
   • grid[p] ^= 1
   • \(C_k > 1\) なら grid[p-1] ^= 1（左）
   • \(C_k < W\) なら grid[p+1] ^= 1（右）
   • \(R_k > 1\) なら grid[p-W] ^= 1（上）
   • \(R_k < H\) なら grid[p+W] ^= 1（下）
4. 最後に grid を \(W\) 文字ずつに区切り、改行を挟んで一括出力する。

具体例

\(H = W = 3\)、初期状態が

000
000
000

のとき、\((2,2)\) のスイッチを押すと \(p = 1\cdot 3 + 1 = 4\) で、\(p, p-1, p+1, p-3, p+3\) = \(4, 3, 5, 1, 7\) が反転し、

010
111
010

となります。さらに \((1,1)\) を押すと \(p = 0\)、左と上は範囲外なので \(0, 1, 3\) が反転し、

100
011
010

です。

計算量

• 時間計算量: \(O(HW + Q)\)
• 空間計算量: \(O(HW)\)

\(HW \le 10^6\)、\(Q \le 10^5\) なので十分高速です。

実装のポイント

• 入出力を高速化する: \(HW \le 10^6\) かつ \(Q \le 10^5\) なので、input() を毎行呼ぶのは遅いです。sys.stdin.buffer.read().split() で全入力を一気に読み、出力も bytearray に溜めて sys.stdout.buffer.write で一度に書き出します。

• 2 次元リストではなく 1 次元 bytearray: リストのリストにするとメモリと参照コストが増えます。\(p = (i-1)W + (j-1)\) の添字計算で 1 次元化すると高速かつ省メモリです。

• ASCII の性質を利用した反転: '0'(48) と '1'(49) は最下位ビットのみ異なるので ^= 1 で反転できます。int 変換や str 生成が不要になり、出力もそのまま行えます。

• 境界判定を忘れない: 端のマスでは隣接マスが存在しません。特に \(1\) 次元化しているため、c == 1 のときに p-1 を触ると前の行の末尾を誤って反転してしまいます（範囲外エラーにならず WA になるので危険です）。if c > 1, if c < W, if r > 1, if r < H の \(4\) つの判定を必ず入れましょう。

• \(W\) は入力から直接与えられない場合に注意: 制約に \(W\) の上限は明示されていませんが \(HW \le 10^6\) なので、\(W\) 自体は \(10^6\) まであり得ます。\(H = 1\) の細長いケース、\(W = 1\) の縦長ケースの両方が境界判定で正しく動くか確認しましょう。

• 出力の連結: 行ごとに print を \(H\) 回（最大 \(2\times10^4\) 回）呼ぶのも遅いので、memoryview でスライスしながら bytearray に追記し、最後にまとめて出力するのが安全です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0]); W = int(data[1])
    grid = bytearray(b''.join(data[2:2 + H]))
    Q = int(data[2 + H])
    idx = 3 + H
    for _ in range(Q):
        r = int(data[idx]); c = int(data[idx + 1]); idx += 2
        p = (r - 1) * W + (c - 1)
        grid[p] ^= 1
        if c > 1:
            grid[p - 1] ^= 1
        if c < W:
            grid[p + 1] ^= 1
        if r > 1:
            grid[p - W] ^= 1
        if r < H:
            grid[p + W] ^= 1
    mv = memoryview(grid)
    out = bytearray()
    for i in range(H):
        out += mv[i * W:(i + 1) * W]
        out += b'\n'
    sys.stdout.buffer.write(bytes(out))

main()

---

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