概要

\(H \times W\) のグリッド上の各マスに電球があり、指定されたマスのスイッチを押すとそのマスと上下左右の隣接マスの電球が反転します。\(Q\) 回の操作後の各電球の状態を求める問題です。

考察

素朴なシミュレーションで十分か？

一見「クエリごとにグリッドを更新する」というのは重い処理に思えますが、この問題では 1 回の操作で状態が変化するマスは最大 5 個だけ です。したがって \(Q\) 回の操作で変化するマスの総数は最大 \(5Q = 5 \times 10^5\) 個にすぎません。

つまり、素朴に「押されたマスとその 4 近傍を反転する」を毎回やるだけで、操作部分は \(O(Q)\) で終わります。難しいアルゴリズム（差分累積・imos 法など）は不要です。

では何が難しいのか？

この問題の本質的な難所は 入出力のサイズ です。

• グリッドのサイズは \(H \times W \leq 10^6\) なので、入力は最大約 \(10^6\) 文字、出力も約 \(10^6\) 文字（改行含めて約 \(10^6 + H\) 文字）になります。
• さらに \(H \leq 2 \times 10^4\) という制約はあるものの \(W\) の上限は \(H \times W \le 10^6\) から間接的に決まるだけなので、\(H = 1, W = 10^6\) のような「横に長い」形も、\(H = 2\times10^4, W = 50\) のような形もあり得ます。

このサイズだと、

• 1 文字ずつ cin >> ch / cout << ch する
• 出力を 1 行ずつ endl でフラッシュする
• 文字列連結を毎回行う

といった実装をすると、計算量的には \(O(HW)\) でも定数倍が重く TLE になり得ます。

反転の表現

電球の状態は 0/1 なので、反転は XOR 1（^= 1）で表せます。「押した回数の偶奇だけが効く」ことも XOR の性質から自然に分かりますが、今回はそもそも直接反転してしまえば良いので偶奇を数える必要すらありません。

具体例

\(H = 3, W = 3\) で

000
000
000

に対してマス \((2,2)\) のスイッチを押すと

010
111
010

となり、続けて \((1,2)\) を押すと、\((1,1),(1,2),(1,3),(2,2)\) が反転して

101
101
010

になります（\((1,2)\) の上は存在しないので何もしない）。境界の外にはみ出す部分を処理しないことがポイントです。

アルゴリズム

1. グリッドを 1 次元配列 g として持つ。マス \((i, j)\)（0-indexed）は g[i * W + j] に対応させる。
2. 入力文字列を読みながら g に 0/1 を格納する。
3. 各クエリ \((R_k, C_k)\) について、0-indexed に直した idx = r * W + c として
   • g[idx] ^= 1
   • r > 0 なら g[idx - W] ^= 1（上）
   • r < H-1 なら g[idx + W] ^= 1（下）
   • c > 0 なら g[idx - 1] ^= 1（左）
   • c < W-1 なら g[idx + 1] ^= 1（右）

境界判定は必ず「行・列の番号」で行うこと（idx だけで判定すると、行をまたいで左右が繋がってしまう）。 4. 最後に g を 1 つの大きな文字バッファに詰めて一気に出力する。

計算量

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

\(HW \le 10^6\), \(Q \le 10^5\) なので余裕で間に合います。

実装のポイント

• 2 次元配列ではなく 1 次元配列を使う: \(H, W\) が実行時に決まるうえ、\(H \times W \le 10^6\) という「積」の制約なので、vector<vector<char>> より vector<char>（サイズ \(H \times W\)）を 1 本用意して i * W + j でアクセスするのが素直で高速です。インデックスは \(10^6\) 程度なので int でも足りますが、念のため size_t にキャストしておくと安全です。

• 高速入力: 本コードでは fread で一括読み込みしてから自前でパースしています。数値は readInt()、グリッド行は '0'/'1' が来るまでスキップしてから \(W\) 文字読む、という形にすると改行や空白の扱いを気にせず済みます。C++ で cin を使う場合も ios::sync_with_stdio(false); cin.tie(nullptr); を必ず入れ、グリッドは string 単位で読むようにしましょう。

• 高速出力: 出力を for で 1 文字ずつ cout << すると遅くなりがちです。H * (W + 1) 文字分のバッファ（各行の末尾に改行 1 文字）を確保して詰め込み、最後に fwrite 1 回で出すのが確実です。endl は絶対に使わないこと（毎回フラッシュされます）。

• 境界判定のミス: 一番ありがちなバグは、左右の隣接を idx - 1, idx + 1 として列の範囲チェックを忘れ、行の端で隣の行へ回り込むことです。c > 0 と c < W - 1 のチェックを忘れないようにしましょう。また \(W = 1\) や \(H = 1\) のケースでも正しく動くか確認しておくと安心です。

• 反転は XOR: g[idx] = 1 - g[idx] でも良いですが、g[idx] ^= 1 が簡潔で速いです。

  ソースコード

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

static char buf[1 << 25];
static size_t bufLen = 0, bufPos = 0;

static inline int gc() {
    if (bufPos == bufLen) {
        bufLen = fread(buf, 1, sizeof(buf), stdin);
        bufPos = 0;
        if (bufLen == 0) return -1;
    }
    return (unsigned char)buf[bufPos++];
}

static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

int main() {
    int H = readInt();
    int W = readInt();
    vector<char> g((size_t)H * W);
    for (int i = 0; i < H; i++) {
        int c = gc();
        while (c != '0' && c != '1') c = gc();
        size_t base = (size_t)i * W;
        for (int j = 0; j < W; j++) {
            g[base + j] = (char)(c - '0');
            c = gc();
        }
    }
    int Q = readInt();
    for (int k = 0; k < Q; k++) {
        int r = readInt() - 1;
        int c = readInt() - 1;
        size_t idx = (size_t)r * W + c;
        g[idx] ^= 1;
        if (r > 0) g[idx - W] ^= 1;
        if (r < H - 1) g[idx + W] ^= 1;
        if (c > 0) g[idx - 1] ^= 1;
        if (c < W - 1) g[idx + 1] ^= 1;
    }
    // output
    size_t outSize = (size_t)H * (W + 1) + 1;
    vector<char> out(outSize);
    size_t p = 0;
    for (int i = 0; i < H; i++) {
        size_t base = (size_t)i * W;
        for (int j = 0; j < W; j++) out[p++] = (char)('0' + g[base + j]);
        out[p++] = '\n';
    }
    fwrite(out.data(), 1, p, stdout);
    return 0;
}

---

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