Official
D - 照明の切り替え / Switching the Lights Editorial by admin
DeepSeek V3概要
各照明のスイッチを指定された長方形領域内で反転させる操作を繰り返し行った後、すべての照明の明るさの合計を求める問題です。
考察
素朴なアプローチでは、各操作ごとに長方形領域内のすべての照明に対してスイッチ操作を記録しようとすると、1回の操作で最大 \(N \times M\) 個の要素を更新することになり、全体で \(O(Q \times N \times M)\) の計算量が必要です。制約条件 \(N, M \leq 1500\) および \(Q \leq 200000\) を考えると、これは \(1500 \times 1500 \times 200000 = 4.5 \times 10^{11}\) 回もの操作が必要になり、現実的な時間で計算することはできません。
そこで、効率的に各照明のスイッチが押された回数を求めるために、二次元累積和(または二次元いもす法)を利用します。各操作に対して長方形領域の四隅にのみマークをつけ、最後に累積和を取ることで、各照明のスイッチが押された回数を効率的に計算できます。
アルゴリズム
- 二次元差分配列の作成: サイズ \((N+2) \times (M+2)\) の配列
diffを作成します(+2は範囲外アクセスを防ぐため)。 - 操作の記録: 各操作 \((r1, c1, r2, c2)\) に対して、以下の4点を更新します:
diff[r1][c1] += 1diff[r1][c2+1] -= 1diff[r2+1][c1] -= 1diff[r2+1][c2+1] += 1
- 累積和の計算: 二次元累積和を計算し、各照明 \((i, j)\) がスイッチを押された回数
total_switches[i][j]を求めます。 - 明るさの計算: 各照明について、スイッチが押された回数が奇数なら明るさを \(2 \times B_{i,j}\)、偶数なら \(B_{i,j}\) として合計を計算します。
計算量
- 時間計算量: \(O(N \times M + Q)\)
- 累積和の計算に \(O(N \times M)\)、操作の記録に \(O(Q)\) かかります。
- 空間計算量: \(O(N \times M)\)
- 差分配列と累積和配列を保持するためです。
実装のポイント
配列のインデックスに注意: 入力のグリッドは0-indexedですが、差分配列は1-indexedで扱っています。
範囲外アクセスを防ぐため、配列のサイズを \((N+2) \times (M+2)\) としています。
累積和を計算する際は、左上から順に
total_switches[i][j] = diff[i][j] + total_switches[i-1][j] + total_switches[i][j-1] - total_switches[i-1][j-1]という式を使います。ソースコード
def main():
import sys
data = sys.stdin.read().split()
idx = 0
N = int(data[idx]); M = int(data[idx+1]); Q = int(data[idx+2]); idx += 3
grid = []
for i in range(N):
row = list(map(int, data[idx:idx+M]))
idx += M
grid.append(row)
diff = [[0] * (M+2) for _ in range(N+2)]
for i in range(Q):
r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
diff[r1][c1] += 1
diff[r1][c2+1] -= 1
diff[r2+1][c1] -= 1
diff[r2+1][c2+1] += 1
total_switches = [[0] * (M+2) for _ in range(N+2)]
for i in range(1, N+1):
for j in range(1, M+1):
total_switches[i][j] = diff[i][j] + total_switches[i-1][j] + total_switches[i][j-1] - total_switches[i-1][j-1]
ans = 0
for i in range(1, N+1):
for j in range(1, M+1):
switches = total_switches[i][j]
if switches % 2 == 0:
ans += grid[i-1][j-1]
else:
ans += 2 * grid[i-1][j-1]
print(ans)
if __name__ == "__main__":
main()
この解説は deepseekv3 によって生成されました。