ペペロの処分

初期方向が右なら$s_i=1$、それ以外なら$s_i=0$とする。最終方向の指標$c_i$も同様に定め、左と右に渡した回数を$l_i,r_i$とする。方向が交互に変わるので$r_i-l_i=s_i-c_i$である。

$P_i=\sum_{j\leq 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,l_i+s_i-(P_i-L)\geq1$ならとしてを1減らし、そうでなければとする。その後と更新する。答えはである。

貪欲法の正当性を示す。$Y_i=\sum_{j\leq i}c_j,H_i=\sum_{j\leq i}s_j,Q_i=\sum_{j\leq i}P_j$とすると、非負条件は

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

となる。$P_i$は単調増加するため、$U_i$は最初に単調増加し、その後単調減少して、最後に必要な最終右向きの人数となる。したがって、その人数を超えずに置ける1を早く置いても、後の上限を破らない。実現可能な最終状態と接頭辞ごとに比較すると、貪欲法が1を置く時点は遅くならず、必要な個数を必ず置ける。すべての出発回数は非負となり、境界条件も満たす。

求めた回数が実行可能であることも示す。操作した人の最後の出発方向は最終方向の逆である。道グラフで最後の出発方向が閉路を作るのは、隣り合う人の最終方向が左、右となる場合だけである。この変化を貪欲法が作る場合、$r_i=0$または$l_{i+1}=0$となり、少なくとも一方は一度も操作していない。よって操作した人たちの最後の出発方向には閉路がない。

任意の合法な実行は計算した回数を超えない。初めて上限を超えようとする人は、隣から受け取った数が予定以下なので、保存則によりペペロを持っていない。逆に終了時に予定された出発が残れば、残りの出発は各頂点で流入と流出が等しく、ごみ箱へは向かわない。残りの最後の出発をたどると閉路ができ、矛盾する。したがってすべての合法な実行の操作回数が等しく、求めた和が最小値である。

時間・空間計算量は$O(N)$である。64ビット符号付き整数を使う。$C=\sum A_i$とすると$l_i\leq iC+i-1$なので、答えは以下である。

Solution written by GPT6.1