概要

各操作で、押されたスイッチのマスと上下左右のマスの電球を反転させます。影響するマスは最大 \(5\) 個なので、操作をそのまま順番にシミュレーションすれば解けます。

考察

重要なのは、スイッチを \(1\) 回押しても、状態が変わる電球は最大 \(5\) 個しかないことです。

操作のたびにすべてのマスを調べて、反転の対象かどうかを判定すると、時間計算量は \(O(QHW)\) になります。制約の最大値では \(10^{11}\) 回程度の判定が必要になり、間に合いません。

そこで、押されたマスと上下左右のマスだけを直接調べます。これなら、各操作で調べるマスは高々 \(5\) 個です。

例えば、\(3 \times 3\) のマス目で \((1,1)\) のスイッチを押すと、反転するのは次の \(3\) マスです。

• 押されたマス \((1,1)\)
• 下のマス \((2,1)\)
• 右のマス \((1,2)\)

上と左にはマスがないため、何もしません。このように、反転する前にマス目の範囲内か確認する必要があります。

また、同じ電球を \(2\) 回反転すると元の状態に戻ります。同じスイッチが複数回押されても、操作のたびに反転させれば正しく処理でき、特別な対応は不要です。

アルゴリズム

1. 初期状態を文字列の配列 \(S\) に保存します。
2. \(Q\) 回の操作を入力された順に処理します。
   1. スイッチの座標を読み取り、配列に合わせて行・列からそれぞれ \(1\) を引きます。
   2. 押されたマスからの相対位置として、次の \(5\) 通りを調べます。
      • 自分自身：\((0,0)\)
      • 上：\((-1,0)\)
      • 下：\((1,0)\)
      • 左：\((0,-1)\)
      • 右：\((0,1)\)
   3. 対象のマスが範囲内にあれば、文字を 0 から 1、または 1 から 0 に変更します。
3. すべての操作が終了したら、\(S\) を行ごとに出力します。

各操作では、問題文で指定されたマスだけをちょうど \(1\) 回ずつ反転しています。したがって、操作後の \(S\) は常にその時点の電球の状態を表し、最後に出力する \(S\) が求める答えになります。

計算量

• 時間計算量: \(O(HW + Q)\)
  • 初期状態の入力と最終状態の出力に \(O(HW)\) かかります。
  • 各操作では高々 \(5\) マスを調べるため、全操作で \(O(Q)\) かかります。
• 空間計算量: \(O(HW)\)
  • 電球の状態を文字列の配列として保持します。操作は読み込むたびに処理するため、保存する必要はありません。

実装のポイント

• 座標を \(0\) 始まりにそろえる
  入力は \(1\) 始まりですが、C++ の配列や文字列は \(0\) 始まりです。コードでは --r; --c; で変換しています。

• 方向配列に自分自身も含める
  dr と dc の先頭にそれぞれ 0 を入れることで、押されたマス自身も同じループで処理できます。

• 配列にアクセスする前に範囲を確認する
  対象座標を \((nr,nc)\) とすると、\(0 \leq nr < H\) かつ \(0 \leq nc < W\) の場合だけ反転します。これにより、端のマスや \(H=1\)、\(W=1\) の場合も正しく扱えます。

• 文字として反転する
  \(S\) の各要素は文字なので、数値の 0・1 ではなく、文字の '0'・'1' を使います。

  ソースコード

#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    for (auto& row : S) cin >> row;

    int Q;
    cin >> Q;

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

    while (Q--) {
        int r, c;
        cin >> r >> c;
        --r;
        --c;

        for (int d = 0; d < 5; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (0 <= nr && nr < H && 0 <= nc && nc < W) {
                S[nr][nc] = (S[nr][nc] == '0' ? '1' : '0');
            }
        }
    }

    for (const auto& row : S) cout << row << '\n';
    return 0;
}

---

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