概要

\(H \times W\) のマス目において、指定されたマスのスイッチを押して自身と上下左右の電球を反転させる操作を \(Q\) 回行った後、最終的な各マスの電球の状態（点灯: 1、消灯: 0）を求める問題です。

考察

1. 操作の重要な性質

電球の反転操作には、以下の重要な性質があります。 - 偶数回反転すると元の状態に戻る: ある電球を 2 回反転させると元の状態に戻ります。したがって、最終的な状態に影響を与えるのは「反転した回数が奇数回か偶数回か（パリティ）」のみです。 - 操作の順番は結果に影響しない: どの順番でスイッチを押しても、最終的に各マスが反転する回数は変わりません。

2. スイッチが押された回数の偶奇に着目する

同じマスのスイッチを 2 回押すことは、0 回押した（1 回も押していない）ことと同じです。 そのため、各マス \((i, j)\) について「スイッチが最終的に奇数回押されたか、偶数回押されたか」だけを記録しておけば十分です。

3. 各電球が反転する条件

マス \((i, j)\) の電球に影響を与えるのは、以下のスイッチのみです。 - マス \((i, j)\) 自身のスイッチ - マス \((i, j)\) の上下左右に隣接するマスのスイッチ

したがって、マス \((i, j)\) の電球が最終的に反転するかどうかは、「自身および上下左右の隣接マスのうち、スイッチが奇数回押されたマスの個数」の合計が奇数か偶数かによって決まります。

【具体例】 マス \((i, j)\) について： - 自身のスイッチが 1 回押された - 上のスイッチが 1 回押された - 右のスイッチが 2 回（実質 0 回）押された - 左・下のスイッチは押されていない（0 回）

この場合、影響を与えるスイッチの押下回数の合計は \(1 + 1 + 0 + 0 + 0 = 2\) 回（偶数回）となります。偶数回反転するため、マス \((i, j)\) の電球の状態は初期状態から変化しません。

アルゴリズム

1. スイッチ押下状態の記録:
   • \(H \times W\) の配列 pressed を用意し、すべて \(0\) で初期化します。
   • \(Q\) 回の各クエリ \((R_k, C_k)\) に対し、pressed[R_k][C_k] の値を反転（0 と 1 を切り替え、XOR 1）させます。
2. 最終状態の計算:
   • 各マス \((i, j)\) について、自身および上下左右に隣接するマス \((ni, nj)\) の pressed の値の XOR 和（合計の偶奇）を計算します。
   • XOR 和が \(1\)（奇数回）であれば、初期状態の文字 \(S_i[j]\) を反転（0 なら 1、1 なら 0）させます。
3. 結果の出力:
   • 更新された文字列 \(S\) を順番に出力します。

計算量

• 時間計算量: \(O(HW + Q)\)
  • クエリの処理: 各スイッチの押下回数の偶奇を \(O(1)\) で更新するため、全体で \(O(Q)\) です。
  • 最終状態の計算: 全 \(H \times W\) マスについて、上下左右高々 4 方向を調べるため \(O(HW)\) です。
  • 制約より \(HW \le 10^6, Q \le 10^5\) であるため、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(HW)\)
  • グリッドの電球の状態 \(S\) およびスイッチの押下状態 pressed を保持するために \(O(HW)\) のメモリを使用します。

実装のポイント

• 0-indexed への変換: 問題文の入力は 1-indexed（\(1 \leq R_k \leq H\)、\(1 \leq C_k \leq W\)）で与えられるため、受け取った際に \(1\) を引いて 0-indexed に直して処理すると、配列の範囲外参照を防ぎやすくなります。

• 方向配列の利用: 上下左右の移動量を dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0} のように配列で保持しておくと、ループを使って隣接マスの探索を簡潔に実装できます。

• 高速な入出力: \(H \times W \leq 10^6\) と入力・出力のサイズが大きいため、C++ では cin.tie(nullptr); ios::sync_with_stdio(false); を使用し、改行に endl ではなく \n を用いて高速化を行いましょう。

  ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<string> S(H);
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }

    int Q;
    cin >> Q;

    vector<vector<int>> pressed(H, vector<int>(W, 0));
    for (int k = 0; k < Q; ++k) {
        int r, c;
        cin >> r >> c;
        --r; --c;
        pressed[r][c] ^= 1;
    }

    const int dr[] = {0, 0, 1, -1};
    const int dc[] = {1, -1, 0, 0};

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int flips = pressed[i][j];
            for (int d = 0; d < 4; ++d) {
                int ni = i + dr[d];
                int nj = j + dc[d];
                if (0 <= ni && ni < H && 0 <= nj && nj < W) {
                    flips ^= pressed[ni][nj];
                }
            }
            if (flips) {
                S[i][j] = (S[i][j] == '0' ? '1' : '0');
            }
        }
    }

    for (int i = 0; i < H; ++i) {
        cout << S[i] << "\n";
    }

    return 0;
}

---

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