概要

\(H \times W\) のマス目に対して、指定されたマスのスイッチを押して自身と上下左右の電球を反転させる操作が \(Q\) 回行われます。すべての操作が終わった後の各マスの電球の状態を求める問題です。

考察

重要な気づき

この問題には、スイッチと電球の反転操作に関する \(2\) つの重要な性質があります。

1. 操作の順序は結果に影響しない（可換性）
2. 同じスイッチを \(2\) 回押すと元に戻る（偶奇性）

各電球 \((r, c)\) の最終的な状態は、「その電球を反転させるスイッチ群」が合計で奇数回押されたか、偶数回押されたかだけで決まります。 電球 \((r, c)\) を反転させるスイッチは、マス \((r, c)\) 自身およびその上下左右に隣接するマス（最大 \(5\) 箇所）のスイッチです。

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

クエリごとに毎回 \(5\) マスを走査して状態を更新していくと、実装言語やデータ構造によっては操作ごとのオーバーヘッドが大きくなります。また、文字列の生成や境界判定を毎回行うと定数倍が重くなり、制限時間に間に合わなくなる（TLE）リスクが高まります。

解決策

あらかじめ電球を更新するのではなく、「どのスイッチが何回押されたか」 だけを記録します。さらに、偶数回押されたスイッチは実質 \(0\) 回、奇数回押されたスイッチは実質 \(1\) 回押されたことと同じであるため、記録すべき値は各スイッチの「押された回数の偶奇（0 または 1）」のみです。

1. すべてのクエリを処理し、各スイッチが押された回数の偶奇を求める。
2. その後、各電球 \((r, c)\) について、自身と上下左右の計 \(5\) マスのスイッチの偶奇の合計（排他的論理和: \(\text{XOR}\)）を計算し、初期状態を反転させるべきかを一括で判定する。

これにより、クエリ処理と最終状態の計算を独立して効率的に行うことができます。

アルゴリズム

1. スイッチの押下回数の偶奇を記録する配列の用意 サイズ \((H + 2) \times (W + 2)\) の配列 cnt を \(0\) で初期化します。グリッドの外周に \(1\) マス分の余白（番兵）を持たせることで、端のマスでも範囲外参照を気にせず一律に上下左右を参照できるようにします。

2. クエリの処理 \(Q\) 回の操作それぞれについて、入力されたマス \((R_k, C_k)\) のスイッチの状態を反転させます（cnt[R_k][C_k] ^= 1）。

3. 各マスの電球の状態を決定 各マス \((r, c)\) (\(1 \leq r \leq H, 1 \leq c \leq W\)) について、自身と上下左右のスイッチの押下回数の偶奇の和を求めます。 $\(\text{flip} = cnt[r][c] \oplus cnt[r-1][c] \oplus cnt[r+1][c] \oplus cnt[r][c-1] \oplus cnt[r][c+1]\)$

   • \(\text{flip} = 1\) の場合：初期状態から反転（0 \(\to\) 1、1 \(\to\) 0）
   • \(\text{flip} = 0\) の場合：初期状態のまま

4. すべての行の結果を結合して出力します。

計算量

• 時間計算量: \(O(HW + Q)\)
  • クエリの処理に \(O(Q)\) かかります。
  • 最終的な盤面の計算では、\(H \times W\) マスそれぞれについて周囲 \(5\) マスを確認するため \(O(HW)\) かかります。
  • \(H \times W \leq 10^6\)、\(Q \leq 10^5\) であるため、実行時間制限に十分余裕を持って間に合います。
• 空間計算量: \(O(HW)\)
  • サイズ \((H + 2) \times (W + 2)\) のグリッド情報および答えの文字列を保持するため、\(O(HW)\) のメモリを使用します。

実装のポイント

• 番兵（パディング）による境界判定の省略 グリッドの上下左右に \(1\) 行/\(1\) 列分の余白を持たせることで、「\(1 \leq r \leq H\) かつ \(1 \leq c \leq W\)」といった境界判定の if 文をなくし、コードを簡潔にしつつ実行速度を向上させています。

• 1次元配列でのフラットな管理 Python では 2 次元の list を使うよりも、1 次元の配列（インデックス r * (W + 2) + c）として管理する方がメモリアクセスが高速になります。

• bytearray と ASCII コードの XOR を用いた高速化 文字 '0' の ASCII コードは \(48\)（\(2\) 進数で ...00）、'1' は \(49\)（\(2\) 進数で ...01）です。 最下位ビットのみが異なるため、文字コードに対して \(\text{flip}\)（\(0\) または \(1\)）を \(\text{XOR}\) 演算するだけで、'0' と '1' の反転を高速に行うことができます（例: \(48 \oplus 1 = 49\)、 \(49 \oplus 1 = 48\)）。

  ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    H = int(input_data[0])
    W = int(input_data[1])

    ptr = 2
    S = input_data[ptr : ptr + H]
    ptr += H

    Q = int(input_data[ptr])
    ptr += 1

    W2 = W + 2
    cnt = bytearray((H + 2) * W2)

    RC = input_data[ptr:]
    for i in range(0, 2 * Q, 2):
        r = int(RC[i])
        c = int(RC[i + 1])
        cnt[r * W2 + c] ^= 1

    ans = []
    for r in range(1, H + 1):
        s_row = S[r - 1].encode("ascii")
        res_row = bytearray(W)
        base = r * W2
        for c in range(1, W + 1):
            idx = base + c
            flip = (
                cnt[idx]
                ^ cnt[idx - 1]
                ^ cnt[idx + 1]
                ^ cnt[idx - W2]
                ^ cnt[idx + W2]
            )
            res_row[c - 1] = s_row[c - 1] ^ flip
        ans.append(res_row.decode("ascii"))

    sys.stdout.write("\n".join(ans) + "\n")


if __name__ == "__main__":
    main()

---

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