D - 照明の切り替え / Switching the Lights 解説 by admin
Claude 4.6 Opus (Thinking)概要
\(N \times M\) のグリッド上の照明に対して \(Q\) 回の長方形領域スイッチ操作を行い、各照明が奇数回押されたか偶数回押されたかに応じて明るさを計算し、合計を求める問題です。
考察
重要な気づき:偶奇だけが重要
各照明の最終的な明るさは、スイッチが押された回数の偶奇だけで決まります。奇数回なら明るさは \(2 \times B_{i,j}\)、偶数回なら \(B_{i,j}\) です。具体的な回数を正確に数える必要はなく、奇数か偶数かだけ分かればよいのです。
素朴なアプローチの問題点
\(Q\) 回の操作それぞれで、指定された長方形領域内のすべての照明を1つずつ更新すると、1回の操作で最大 \(N \times M = 1500 \times 1500 = 2.25 \times 10^6\) セルを処理することになります。\(Q\) 回合わせると最大 \(Q \times N \times M \approx 4.5 \times 10^{11}\) 回の処理が必要となり、到底間に合いません。
解決策:2次元いもす法(XOR版)
通常の2次元いもす法(累積和の逆操作としての差分配列)では、長方形領域への加算を4点への操作に圧縮できます。今回は回数の偶奇だけが重要なので、加算の代わりに XOR を使います。XOR は \(0 \oplus 1 = 1\)、\(1 \oplus 1 = 0\) と偶奇の切り替えに対応するため、累積和の代わりに累積 XOR を取ればよいのです。
アルゴリズム
- 差分配列の構築: サイズ \((N+2) \times (M+2)\) の差分配列
diffを \(0\) で初期化します。各操作 \((r1, c1, r2, c2)\) に対して、以下の4点を XOR で更新します:diff[r1][c1] ^= 1diff[r1][c2+1] ^= 1diff[r2+1][c1] ^= 1diff[r2+1][c2+1] ^= 1
これは通常の2次元いもす法で +1 する代わりに XOR 1 しているだけです。
- 累積 XOR の復元: まず行方向(左から右)に累積 XOR を取り、次に列方向(上から下)に累積 XOR を取ります。これにより、
diff[i][j]にセル \((i, j)\) のスイッチが押された回数の偶奇(\(0\) or \(1\))が格納されます。
具体例: 3×3 グリッドで操作 \((1,1,2,2)\) を1回行った場合、差分配列の4隅に \(1\) が立ち、累積 XOR 後に \((1,1)\)〜\((2,2)\) の範囲だけが \(1\) になります。
- 合計の計算: 各セル \((i, j)\) について、
diff[i][j]が \(1\)(奇数回)なら \(2 \times B_{i,j}\)、\(0\)(偶数回)なら \(B_{i,j}\) を合計に加えます。
計算量
- 時間計算量: \(O(N \times M + Q)\)
- 差分配列への更新は各操作 \(O(1)\) で合計 \(O(Q)\)
- 累積 XOR の復元と合計計算が \(O(N \times M)\)
- 空間計算量: \(O(N \times M)\)
- 差分配列とグリッドの格納
実装のポイント
XOR によるいもす法: 偶奇だけが必要な場合、加算と累積和の代わりに XOR と累積 XOR を使えます。XOR は
a ^= bで簡潔に書けます。配列サイズに注意: 差分配列は
r2+1やc2+1にアクセスするため、\((N+2) \times (M+2)\) のサイズを確保する必要があります。高速入力: \(N, M\) が最大 1500 で \(Q\) が最大 \(2 \times 10^5\) と大きいため、Python では
sys.stdin.buffer.read()で一括読み込みすることで入力を高速化しています。ソースコード
import sys
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
Q = int(input_data[idx]); idx += 1
B = []
for i in range(N):
row = [int(input_data[idx + j]) for j in range(M)]
idx += M
B.append(row)
# 2D difference array for counting switch presses (parity)
# Using imos method on (N+2) x (M+2) grid
diff = [[0] * (M + 2) for _ in range(N + 2)]
for _ in range(Q):
r1 = int(input_data[idx]); idx += 1
c1 = int(input_data[idx]); idx += 1
r2 = int(input_data[idx]); idx += 1
c2 = int(input_data[idx]); idx += 1
diff[r1][c1] ^= 1
diff[r1][c2 + 1] ^= 1
diff[r2 + 1][c1] ^= 1
diff[r2 + 1][c2 + 1] ^= 1
# Compute prefix XOR row-wise then column-wise
for i in range(1, N + 1):
for j in range(1, M + 1):
diff[i][j] ^= diff[i][j - 1]
for j in range(1, M + 1):
for i in range(1, N + 1):
diff[i][j] ^= diff[i - 1][j]
total = 0
for i in range(1, N + 1):
for j in range(1, M + 1):
b = B[i - 1][j - 1]
if diff[i][j] & 1:
total += 2 * b
else:
total += b
print(total)
main()
この解説は claude4.6opus-thinking によって生成されました。