BOJ 10350. Banks
문제 해석
정수 \(x_0..x_{n-1}\)이 원형으로 나열되어 있다. 이 수열에 정의된 연산 \(P(k)\)는 \(x_k < 0\)인 \(k\)에 대해 사용 가능하고, 그 효과는 \(x_k\)의 부호를 바꾼 다음 양 옆에 인접한 두 수에서 각각 \(\vert x_k \vert\)를 빼는 것이다. 모든 항을 \(0\) 이상으로 만들기 위해 필요한 \(P\) 연산의 최소 횟수를 구하라.
처음에 \(x_0..x_{n-1}\)의 총합은 양수이다.
접근
모든 (연속) 구간합의 집합 \(S\)를 정의하자. 수열이 원형이므로 시작 위치는 \(0..n-1\)로 제한하지만 길이에는 제한이 없어 \(S\)는 무한집합이다. 시작 위치와 길이 중 하나라도 다르면 합이 같아도 다른 구간합으로 생각할 것이므로 중복집합(multiset)으로 정의한다. 단, 빈 구간합은 \(S\)에 포함시키지 않는다.
\[S := \text{multiset} \{ x_i + \cdots + x_j ;\quad 0 \le i \lt n,\ i \le j \}\]Claim. \(k\)의 값에 관계없이, \(P(k)\)를 1회 하면 \(S\)의 음수 원소 1개의 부호가 바뀌고 나머지 모든 원소는 변하지 않는다.
Proof. 모든 연속 구간합들을 \(x_{k-1}, x_{k}, x_{k+1}\)을 몇 번씩 포함하고 있는지에 따라 분류할 것이다. 이때 인덱스는 \(\mod n\)에서 생각한다. 예를 들어 \(n=10, k=5\)라고 하면, \(i=6\)부터 \(j=24\)까지의 구간합은 \(x_4\)를 \(2\)번 \((x_{14}, x_{24})\), \(x_5\)를 \(1\)번 \((x_{15})\), \(x_6\)을 \(2\)번 \((x_6, x_{16})\) 포함한다. 이런 식으로 나온 횟수들이 \(a,b,c\)번일 때 이 구간합을 \((a,b,c)\)라고 표기하기로 하자.
\(b \le a + c\)인 구간합 \((a,b,c)\)는 \(P(k)\) 실행 후에 \((a,a+c-b,c)\)가 되며, 한 번 더 하면 원래대로 돌아오기 때문에, 모든 구간합들을 둘씩 짝지을 수 있는 게 아닌가 하는 가설을 내볼 수 있다.
그러기 위해 한 가지 추가 관찰로, 임의의 구간합 \((a,b,c)\)에서 \(a,b,c\) 중 어느 둘의 차이가 \(1\)보다 클 수 없음을 확인하자. \(i\)를 고정하고 \(j\)를 늘려 보면 \(a,b,c\)가 돌아가면서 \(1\)씩 커지기 때문. 따라서 임의의 구간합 \((a, b, c)\)는 아래의 꼴을 가진다.
\[\begin{align} (a, b, c) = (m + t_a, m + t_b, m + t_c)\\ (m은 0 이상의 정수,\quad t_a, t_b, t_c \in \{0, 1\},\quad t_a \times t_b \times t_c = 0)\\ \end{align}\]\(t_a, t_b, t_c\)의 값에 따라서 \(7\)개의 그룹으로 나눌 수 있다. 편의상 이진법을 이용해 \(G_0..G_6\)이라고 부르자(e.g., \((m, m+1, m+1)\) 꼴은 \(G_3\)에 속한다). \(P(k)\) 연산이 각 그룹을 어떻게 변화시키는지 보자.
\[\begin{align} (m, m, m) &\leftrightarrow (m, m, m)\\ (m, m, m+1) &\leftrightarrow (m, m+1, m+1)\\ (m+1, m, m) &\leftrightarrow (m+1, m+1, m)\\ (m, m+1, m) &\rightarrow (m, m-1, m) \qquad (m > 0 \text{ only})\\ (m+1, m, m+1) &\rightarrow (m+1, m+2, m+1)\\ \end{align}\]\(G_0\)은 변화가 없고, \(G_1:G_3\), \(G_4:G_6\)은 완전한 일대일 대응을 이루므로 이 다섯 그룹의 원소들은 \(P(k)\) 후에도 동일하게 존재한다. 그런데 \(G_2\)에서 \(G_5\)로 갈 때는 \(m\)이 1 감소하고 반대 방향에서는 1 증가하기 때문에 \((0, 1, 0)\)만 빼놓고 엇갈려서 짝이 지어진다. 결국 구간합들이 둘씩 짝지어진다는 가설은 \((0,1,0)\) 1개만 빼고 참인 셈이며, 해당 구간합은 \(x_k\)에서 \(-x_k\)로, 즉 음수에서 양수로 바뀐다. \(\blacksquare\)
수열의 모든 항이 음이 아닌 것은 \(S\)에 음수 원소가 없는 것과 동치이므로, 초기 \(S\)의 음수 원소 개수를 세면 된다. 수열 총합이 양수이므로 \(S\)의 음수 원소 개수는 유한하고, 누적합과 주기성을 이용하면 \(O(n^2)\)에 풀 수 있다.
이 하늘에서 뚝 떨어진 것 같은 풀이는 toysmars님의 블로그[1]에 언급된 것처럼 IMO 1986 3번과 관련이 깊다.