빼빼로 처리

처음 방향이 오른쪽이면 $s_i=1$, 아니면 $s_i=0$으로 두자. 최종 방향을 같은 방식으로 $c_i$로 나타내고, $i$번 사람이 왼쪽과 오른쪽으로 건넨 횟수를 각각 $l_i,r_i$라 하자. 방향이 번갈아 바뀌므로 $r_i-l_i=s_i-c_i$이다.

$P_i=\sum_{j=1}^{i}A_j$, 왼쪽 쓰레기통에 들어간 개수를 이라 하자. 각 경계를 지나는 빼빼로의 수를 세면 이다. 경계 조건은 , 이다. 따라서

$$W=\sum_{i=1}^{N}P_i-\sum_{i=1}^{N}s_i,\qquad (N+1)L=W+\sum_{i=1}^{N}c_i.$$

$0\leq\sum c_i\leq N$이므로 $L=\lceil W/(N+1)\rceil$이며 최종 오른쪽 방향의 수는 이다.

왼쪽부터 $l_i$와 아직 정하지 않은 오른쪽 방향의 수 $K$를 유지한다. $K>0$, $l_i+s_i\geq1$, 이면 로 정하고 를 1 줄인다. 그렇지 않으면 이다. 이후 , 로 갱신한다. 정답은 이다.

이 그리디의 타당성을 보자. $Y_i=\sum_{j\leq i}c_j$, , 라 하면 비음수 조건은

$$Y_i\leq U_i=iL-Q_{i-1}+H_i+\min(0,L-P_i)$$

이다. $P_i$가 단조 증가하므로 $U_i$는 먼저 단조 증가한 뒤 단조 감소하며 마지막 값은 처음 구한 최종 오른쪽 방향의 수이다. 따라서 그 수를 넘지 않으면서 현재 가능한 1을 먼저 선택해도 뒤의 상한을 위반하지 않는다. 가능한 최종 상태와 접두사별로 비교하면 그리디는 그 상태보다 1을 늦게 선택하지 않으므로 정확한 개수의 1을 선택한다. 모든 $l_i,r_i$가 비음수이고 양 끝 경계 조건도 성립한다.

구한 횟수가 실제 실행과 일치함도 확인해야 한다. 한 사람이 마지막으로 건넨 방향은 최종 방향의 반대이다. 일렬 그래프에서 마지막 전달 방향이 만드는 순환은 이웃한 두 사람의 최종 방향이 왼쪽, 오른쪽인 경우뿐이다. 그리디가 이 전환을 만들었다면 $r_i=0$ 또는 $l_{i+1}=0$이므로 두 사람 중 한 명은 한 번도 행동하지 않았다. 따라서 행동한 사람들 사이에는 마지막 전달 방향의 순환이 없다.

임의의 합법적인 실행은 구한 횟수를 초과할 수 없다. 처음으로 횟수를 초과하려는 사람은 이웃에게서 받은 수가 예정된 수 이하이므로 빼빼로를 가지고 있지 않다. 반대로 실행이 끝났는데 예정된 전달이 남아 있다면, 남은 전달들은 각 사람에서 유입과 유출이 같고 쓰레기통으로 나가지 않는다. 남은 마지막 전달을 따라가면 순환이 생겨 앞의 성질과 모순된다. 따라서 모든 합법적인 실행의 행동 횟수가 같으며, 구한 합이 최솟값이다.

시간 복잡도는 $O(N)$, 공간 복잡도는 $O(N)$이다. 합을 저장할 때는 64비트 정수를 사용한다. $C=\sum A_i$라 하면 이므로 정답은 이하이다.

Solution written by GPT6.1