概要

各操作について、押されたスイッチのマスと上下左右のマスの電球を反転させます。操作を順番にシミュレーションし、最後の状態を出力します。

考察

重要なのは、1 回の操作で変化する電球は最大でも 5 個しかないことです。

各操作のたびにすべてのマスを調べると、時間計算量は \(O(QHW)\) となり、制約の最大値では間に合いません。しかし、変化するマスの座標はスイッチの位置から直接求められるため、盤面全体を調べる必要はありません。

例えば、マス \((2, 3)\) のスイッチを押す場合、反転させる候補は次の 5 マスです。

• 自分自身：\((2, 3)\)
• 上：\((1, 3)\)
• 下：\((3, 3)\)
• 左：\((2, 2)\)
• 右：\((2, 4)\)

このうち、マス目の範囲内にあるものだけを反転させます。これなら 1 回の操作を \(O(1)\) 時間で処理できます。

また、同じ電球が複数回反転する場合も、そのたびに状態を更新すれば問題ありません。例えば、消灯している電球を 2 回反転すると、0 → 1 → 0 と元に戻ります。

したがって、特別な前処理は不要で、影響を受けるマスだけを更新する素直なシミュレーションで解けます。

アルゴリズム

1. 初期状態を配列 grid に保存します。
2. 各操作 \((R_k, C_k)\) について、次を行います。
   1. 配列の添字に合わせて、行番号と列番号からそれぞれ \(1\) を引きます。
   2. 押されたスイッチと同じマスの電球を反転します。
   3. 左・右・上・下の各マスについて、マス目の範囲内にあれば電球を反転します。
3. すべての操作を処理した後、grid を行ごとに出力します。

各操作では、問題文で指定されたマスだけをちょうど 1 回ずつ反転しています。そのため、初期状態から操作を順番に適用することで、最終的な電球の状態が正しく求まります。

計算量

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

初期状態の読み込みと最終状態の出力に \(O(HW)\) 時間かかります。各操作では最大 5 マスを更新するだけなので、全操作の処理時間は \(O(Q)\) です。

実装のポイント

bytearray で各マスを直接更新する

Python の文字列は、一部の文字を直接書き換えることができません。そこで、コードでは各行を bytearray として保存しています。

grid = [bytearray(read().strip()) for _ in range(h)]

これにより、grid[r][c] を直接更新できます。

XOR で 0 と 1 を切り替える

bytearray の要素は文字そのものではなく、その文字のバイト値です。0 は \(48\)、1 は \(49\) であり、これらは最下位ビットだけが異なります。

そのため、次の処理で 0 と 1 を切り替えられます。

grid[r][c] ^= 1

隣接マスの範囲を確認する

行番号と列番号を 0 始まりにすると、有効な範囲は \(0 \leq r < H\)、\(0 \leq c < W\) です。

例えば、左のマスは c > 0 の場合にだけ更新します。特に Python では添字 -1 が末尾の要素を指すため、範囲確認を忘れると、エラーにならず別のマスを更新してしまうことに注意してください。

ソースコード

import sys


def main():
    read = sys.stdin.buffer.readline
    h, w = map(int, read().split())
    grid = [bytearray(read().strip()) for _ in range(h)]

    q = int(read())
    for _ in range(q):
        r, c = map(int, read().split())
        r -= 1
        c -= 1

        row = grid[r]
        row[c] ^= 1
        if c > 0:
            row[c - 1] ^= 1
        if c + 1 < w:
            row[c + 1] ^= 1
        if r > 0:
            grid[r - 1][c] ^= 1
        if r + 1 < h:
            grid[r + 1][c] ^= 1

    sys.stdout.buffer.write(b"\n".join(grid) + b"\n")


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。