E - 2xN Grid Editorial by evima
素朴な実装一言で述べると、二つの行をそれぞれ左から右へと見ていけば線形時間で答えを求められます。
より詳しくアルゴリズムを述べると、以下の通りです。
- \(ans = 0, i = 1, j = 1\) と初期化する。
- \(i \leq N\) かつ \(j \leq M\) である限り、以下の一連の手順を繰り返す。
- 二つの「ブロック」\((a_i, b_i), (c_j, d_j)\) を検討する。もし \(a_i = c_j\) なら、\(ans\) にこれらのブロックの「共通部分」の長さを足す。
- もしブロック \((a_i, b_i)\) の右端がブロック \((c_j, d_j)\) の右端より左側にあるなら、\(i\) に \(1\) を足す。そうでないなら、\(j\) に \(1\) を足す。
- \(ans\) を出力する。
実装例(Python)
L, N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
B = [list(map(int, input().split())) for i in range(M)]
ans, i, j, p, q = 0, 0, 0, 0, 0
while i < N and j < M:
if A[i][0] == B[j][0]:
ans += min(p + A[i][1], q + B[j][1]) - max(p, q)
if p + A[i][1] < q + B[j][1]:
p += A[i][1]
i += 1
else:
q += B[j][1]
j += 1
print(ans)
posted:
last update: