ABC337 D - Island Tour

Competitive Programming C++

2024-01-27

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc338/tasks/abc338_d

원문 링크
https://atcoder.jp/contests/abc338/editorial/9171

\(v_i = (다리\ i를\ 봉쇄했을\ 때\ 여행\ 거리의\ 최솟값)\)이라고 두고 이 \(v_i\)를 모든 \(i = 1, 2, …, M\)에 대해 구하는 방법을 생각할 수 있습니다.

여행은 섬 \(X_1 \rightarrow X_2, X_2 \rightarrow X_3, …, X_{M - 1} \rightarrow X_M\)의 \(M - 1\)번의 이동으로 분해할 수 있습니다. 이 이동들은 서로 독립이므로, 순서대로 하나씩 보면서 각각의 이동에 의한 변화량 만큼을 각각의 \(v_i\)에 더해가면 됩니다.

어떤 섬 \(a\)에서 어떤 섬 \(b\)로의 이동에 대해서 생각해 봅시다. 섬 \(a\)부터 \(b\)까지(같은 다리를 여러 번 건너지 않고) 이동하는 방법은, \(a \rightarrow a + 1 \rightarrow a + 2 \rightarrow … \rightarrow b\)로 가는 방법과, \(a \rightarrow a - 1 \rightarrow a - 2 \rightarrow … \rightarrow b\)로 가는 방법의 2가지가 있습니다. 전자를 실행할 때 지나가는 다리의 집합을 \(S\), 후자를 실행할 때 지나가는 다리의 집합을 \(T\)라고 합시다.
여기서 \(S\)와 \(T\)는 공통된 원소를 갖지 않고, 그 합집합은 전체 다리의 집합과 일치합니다.

봉쇄하는 다리가 어느 한 쪽의 집합에 속하는지에 따라서, 다음의 2가지 경우를 생각할 수 있습니다.

• 봉쇄하는 다리가 \(S\)에 속할때: \(T\)의 다리들을 이용해 이동하므로, 이동하는 거리는 \(\mid T \mid\)가 된다.
• 봉쇄하는 다리가 \(T\)에 속할때: \(S\)의 다리들을 이용해 이동하므로, 이동하는 거리는 \(\mid S \mid\)가 된다.
  (집합 \(X\)의 원소의 수를 \(\mid X \mid\)라고 표기합니다)

따라서, 각 \(i \in S\)에 대해 \(v_i\)에 \(\mid T \mid\)를 더하고, 각 \(i \in T\)에 대해 \(\mid S \mid\)를 더하면 됩니다. 설명대로 이 조작을 모두 \(M - 1\)번 실행할 필요가 있으므로, 브루트포스로 하면 시간 제한에 맞출 수 없습니다.
여기서 \(v\)대신 그 차이의 배열인 \(v’ (v_i’ = c_i - v_{i - 1})\)을 관리하는 것으로 생각하면, \([v_l, v{l + 1}, … , v_r에\ x를\ 더한다]\)는 조작은 \([v_l’에\ x를\ 더하고, v_{r + 1}’에\ -x를\ 더한다]\)는 조작으로 치환할 수 있으므로, 각 조작 당 \(O(1)\)에 처리하는 것이 가능합니다. \(M - 1\)개의 이동 모두를 이런 식으로 처리한 후, \(v’\)의 누적 합을 구하는 것으로 원래 목적이었던 배열 \(v\)가 구해집니다. 이런 방법을 소위 imos법이라고 부르기도 합니다.

전체 시간복잡도는 \(O(N)\)입니다.

누적합 문제였다. 맵다.

D가 생각보다 매워서… 처참히 시간을 다 날렸다.
imos법을 D에 가져올줄은…

더 단련하는 수 밖에 없다.