D - 照明の切り替え / Switching the Lights 解説 by admin
Qwen3-Coder-480B概要
\(N \times M\) のグリッド上の各照明について、複数回の矩形領域に対するスイッチ操作が与えられ、最終的な明るさの合計を求める問題です。
考察
各照明のスイッチが奇数回押されると「強調モード」(明るさが2倍)、偶数回押されると「通常モード」(明るさそのまま)になります。したがって、各照明についてスイッチが押された回数の偶奇だけが重要です。
素朴な方法として、各操作ごとに指定された矩形領域内のすべてのマスのカウントを直接更新する方法が考えられます。しかし、操作回数 \(Q\) が最大 \(2 \times 10^5\)、またグリッドサイズも大きい場合、この方法では全体で最大 \(Q \times N \times M\) の計算が必要になり、時間制限に間に合いません(TLE)。
そこで、「2次元いもす法(いもす法の二次元拡張)」というテクニックを使います。これは、区間の加算を効率的に行うための差分更新の手法です。矩形領域へのインクリメントを4つの点に値を設定する操作に変換し、最後に累積和を取ることで各マスのスイッチ回数を求めることができます。これにより、各操作を定数時間で処理でき、全体で高速に解くことが可能になります。
アルゴリズム
入力の読み込み
グリッドの初期明るさ \(B_{i,j}\) と、\(Q\) 個の操作情報を読み込みます。差分配列の準備
\((N+1) \times (M+1)\) のサイズの2次元配列diffを用意します。これは、各操作によるスイッチ回数の増加分を記録するための差分テーブルです。操作の適用(2Dいもす法)
各操作で指定される矩形領域 \((r1, c1)\) から \((r2, c2)\) に対して、以下のように差分を設定します:diff[r1][c1] += 1diff[r1][c2+1] -= 1diff[r2+1][c1] -= 1diff[r2+1][c2+1] += 1
累積和の計算と偶奇判定
diff配列に対して2次元累積和を計算し、各マス \((i, j)\) でのスイッチ操作回数を求めます。その値を2で割った余り(mod 2)が1であれば奇数回、0であれば偶数回押されたことになります。最終的な明るさの計算
各マスについて、偶奇に応じて明るさを \(B_{i,j}\) または \(2 \times B_{i,j}\) として合計します。
計算量
- 時間計算量: \(O(N \times M + Q)\)
- 空間計算量: \(O(N \times M)\)
実装のポイント
座標を0-indexedに変換している点に注意(入力は1-indexed)
差分配列は\((N+1) \times (M+1)\)のサイズにして、境界処理を簡潔にしています
累積和計算時に範囲外アクセスを防ぐために条件分岐を入れています
ソースコード
import sys
input = sys.stdin.read
def main():
data = input().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
Q = int(data[idx]); idx += 1
B = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
B[i][j] = int(data[idx])
idx += 1
# 差分更新用の2D累積和配列
diff = [[0]*(M+1) for _ in range(N+1)]
for _ in range(Q):
r1 = int(data[idx]) - 1; idx += 1
c1 = int(data[idx]) - 1; idx += 1
r2 = int(data[idx]) - 1; idx += 1
c2 = int(data[idx]) - 1; idx += 1
# 2D差分更新
diff[r1][c1] += 1
diff[r1][c2+1] -= 1
diff[r2+1][c1] -= 1
diff[r2+1][c2+1] += 1
# 2D累積和を計算して各セルのスイッチ回数の偶奇を求める
count = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
v = diff[i][j]
if i > 0:
v += diff[i-1][j]
if j > 0:
v += diff[i][j-1]
if i > 0 and j > 0:
v -= diff[i-1][j-1]
diff[i][j] = v
count[i][j] = v % 2
# 各照明の最終的な明るさを計算
total = 0
for i in range(N):
for j in range(M):
if count[i][j] == 1:
total += 2 * B[i][j]
else:
total += B[i][j]
print(total)
if __name__ == "__main__":
main()
この解説は qwen3-coder-480b によって生成されました。