Official
E - Sum = 0 Editorial
by
E - Sum = 0 Editorial
by 
toam
ヒント
次の問題を考えてみましょう．
長さ \(N\) の非負整数列 \(A=(A_1,A_2,\ldots,A_N)\) がある．整数 \(S\) が与えられるので，以下を満たす長さ \(N\) の整数列\(X=(X_1,X_2,\ldots,X_N)\) が存在するか判定し，存在するならば一つ構築せよ．
- \(0\leq X_i\leq A_i\)
- \(\sum X = S\)
存在するためには明らかに \(\sum A\geq S\) が必要です．実はこれが十分でもあります．存在する場合には，前から順番見て行って，貪欲にできるだけ \(X_i\) を大きくすることで構築できます．元の問題でも似たような考えで解くことができます．
\(\sum L>0\) の場合，\(\sum X\geq \sum L>0\) であるため条件を満たす \(X\) は存在しません．同様に \(\sum R<0\) のとき \(\sum X\leq \sum R <0\) であるため条件を満たす \(X\) は存在しません．
そうでないときは条件を満たす \(X\) が存在します．
各 \(i=1,2,\ldots,N\) に対して \(X_i=L_i\) と初期化したうえで，\(i=1,2,\ldots,N\) の順に貪欲に値を決めていくことができます．具体的には，以下の手順を取ることができます．
- \(i=1,2,\ldots\) に対して，\(X_i<R_i\) かつ \(\sum X<0\) を満たしている限り \(X_i\) の値を \(+1\) する．
ただし，これをそのまま行うと間に合いません，\(X_i\) の増分は次のようにして高速に求めることができます．
- \(i=1,2,\ldots\) に対して，\(D_i=\min(R_i-L_i,-\sum X)\) とする．\(X_i\) の値を \(+D_i\) する．
計算量は \(O(N)\) です．
N = int(input())
L, R = [0] * N, [0] * N
for i in range(N):
L[i], R[i] = map(int, input().split())
if sum(L) > 0 or sum(R) < 0:
print("No")
exit()
X = L.copy()
sumX = sum(X)
for i in range(N):
d = min(R[i] - L[i], -sumX)
sumX += d
X[i] += d
print("Yes")
print(*X)
posted:
last update: