D - 照明の切り替え / Switching the Lights Editorial by admin
Gemini 3.1 Pro (Thinking)概要
二次元グリッド上の長方形領域に対する「状態の反転操作」を複数回行った後、各マスの最終状態に応じて値の総和を求める問題です。
考察
スイッチを押す操作は、「奇数回押されたか、偶数回押されたか」だけが重要です。つまり、照明の状態は「通常モード」と「強調モード」の2つしかなく、スイッチを押す操作は状態の反転(排他的論理和、XOR)として捉えることができます。
素朴なアプローチとして、クエリごとに長方形領域内のすべてのマスの状態を更新する方法が考えられます。しかし、この方法では1回のクエリで最大 \(O(NM)\) の時間がかかり、全体で \(O(QNM)\) となります。制約(\(N, M \le 1500, Q \le 2 \times 10^5\))を考慮すると、最悪ケースで約 \(4.5 \times 10^{11}\) 回の計算が必要になり、実行時間超過(TLE)となってしまいます。
この問題を解決するためには、長方形領域に対する一括更新を高速に行う手法である「二次元いもす法」を活用します。通常、いもす法では加算と減算を行いますが、今回は「反転」の操作なので、代わりにXOR(^)を用いることで全く同じように処理できます。
アルゴリズム
二次元いもす法(XOR版) を使用して解を進めます。
差分配列の準備 サイズが \((N+2) \times (M+2)\) の二次元配列
diffを用意し、初期値をすべて \(0\) とします(\(1\)-indexedで扱いやすくするため、少し大きめに確保します)。クエリの処理 各クエリで指定された長方形領域(左上 \((r1, c1)\) 、右下 \((r2, c2)\))に対し、以下の4箇所のフラグを反転(\(1\) とのXOR)させます。
diff[r1][c1] ^= 1(ここから反転を開始)diff[r1][c2+1] ^= 1(列方向の反転を終了)diff[r2+1][c1] ^= 1(行方向の反転を終了)diff[r2+1][c2+1] ^= 1(重複して終了した部分を相殺)
この操作により、各クエリを \(O(1)\) で処理できます。
- 累積和(XOR)の計算と答えの集計
すべてのクエリを処理し終えた後、
diff配列の二次元累積XORを計算します。 上から下へ、左から右へと累積XORを取ることで、各マスの最終的な状態(奇数回押されたなら \(1\) 、偶数回なら \(0\))が確定します。
状態が \(1\)(強調モード)ならば \(2 \times B_{i,j}\) を、状態が \(0\)(通常モード)ならば \(B_{i,j}\) を全体の明るさの合計に加算します。
計算量
- 時間計算量: \(O(NM + Q)\)
- 入力の読み込みと初期化に \(O(NM + Q)\)
- クエリの処理は1回あたり \(O(1)\) なので、全体で \(O(Q)\)
- 累積和の計算と答えの集計に \(O(NM)\)
- 合計で \(O(NM + Q)\) となり、制約下で十分に高速です。
- 空間計算量: \(O(NM)\)
- 照明の初期状態を保持する配列 \(B\) と、差分配列
diffのためにそれぞれ \(O(NM)\) のメモリを使用します。
- 照明の初期状態を保持する配列 \(B\) と、差分配列
実装のポイント
高速な入出力: Pythonでは入力サイズが大きいため、
sys.stdin.read().split()を用いて入力を一括で読み込み、イテレータを使って処理することで実行時間を大幅に短縮しています。累積和の定数倍高速化: 二次元累積和を求める際、縦方向の累積結果(
diff_i[j] ^= diff_prev[j])と横方向の累積結果(変数cur ^= diff_i[j])を1つのループ内で同時に計算することで、配列へのアクセス回数を減らしています。ビットシフトを用いた条件分岐の省略: 最終的な状態
curは \(0\) または \(1\) になります。これを活用し、ans += B_i[j-1] << curと記述することで、if文を使わずに計算しています。<< 0は \(1\) 倍(そのまま)、<< 1は \(2\) 倍を意味するため、非常に簡潔かつ高速に処理できます。ソースコード
import sys
def solve():
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
M = int(input_data[1])
Q = int(input_data[2])
idx = 3
B = [[int(x) for x in input_data[idx + i * M : idx + (i + 1) * M]] for i in range(N)]
idx += N * M
diff = [[0] * (M + 2) for _ in range(N + 2)]
queries = [int(x) for x in input_data[idx:]]
it = iter(queries)
for r1, c1, r2, c2 in zip(it, it, it, it):
diff[r1][c1] ^= 1
diff[r1][c2+1] ^= 1
diff[r2+1][c1] ^= 1
diff[r2+1][c2+1] ^= 1
ans = 0
for i in range(1, N + 1):
cur = 0
diff_i = diff[i]
diff_prev = diff[i-1]
B_i = B[i-1]
for j in range(1, M + 1):
diff_i[j] ^= diff_prev[j]
cur ^= diff_i[j]
ans += B_i[j-1] << cur
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.1-pro-thinking によって生成されました。