abc362-Cを解いてみました

問題

• ある整数$X_i$の上限$R_i$と下限$L_i$が各$i$について与えられる
• このとき，$\sum_i^n X_i = 0$となるような組み合わせの有無を出力
  • あるときは'Yes'と解答例1つを出力
  • ないときは'No'を出力

解法

• $A = \sum_i^n X_i$の上限と下限を出す
  • $m = \sum_i^n L_i$，$M = \sum_i^n R_i$とする
  • $m \leq A \leq M$

$m > 0$または$M < 0$のときは，'Noを出力'

ポイント1: 最大値（最小値でも可）を常に取り続けると考える

• $X_i$として最大値$R_i$を常に取り続けると，$A = M$

このままでは$A = 0$を達成できない

• そこで，どこかの$i$で$X_i = R_i - M$となるような$X_i$を選ぶことができれば，残りの$X_i$で常に最大値をとることで$A = 0$を実現可能

$R_i-M < L_i$だと範囲外なので調整できない

ポイント2: 各 X_i の上限値と下限値の幅を計算

• 各$X_i$について$D_i = R_i - L_i$を計算
• $D_i$をソートし，$D_i$が大きいような$i$から順に以下のループを回す

1. $D_i \geq M $のとき
   • $X_i = R_i - M$として残りの$X_i$で最大値を取り続けて終了
2. $D_i < M$のとき
   • $X_i = L_i$として，残った$X_i$の和で実現可能な最大値$M$を$M-D_i$に更新
3. 次に$D_i$が大きい$i$について次のループへ

$D_i$が大きいほど最大値から ずらしやすいので，大きい順に調べる

実装したコード

• $m$，$M$のうち絶対値が小さい方を0に向かってずらすと楽なので，場合分け
• 計算量のネックは$D_i$のソート部分（$\omicron (n\log n)$）
  • $D_i$のサイズ$n < 2 \times 10^5$であるので，時間内に解ける

n = int(input())
l = [0]*n
r = [0]*n
d = [0]*n
for i in range(n):
  l[i],r[i] = map(int, input().split())
  d[i] = r[i]-l[i]
idxlist = [i[0] for i in sorted(enumerate(d), key=lambda x: x[1], reverse=True)]
upper = sum(r)
lower = sum(l)
ans = [0]*n
if lower > 0 or upper < 0:
  print('No')
else:
  if abs(upper) > abs(lower):
    for idx in idxlist:
      if lower == 0:
        ans[idx] = l[idx]
      elif d[idx] >= abs(lower):
        ans[idx] = l[idx]+(-lower)
        lower = 0
      else:
        ans[idx] = r[idx]
        lower += d[idx]
    if sum(ans) == 0:
      print('Yes')
      print(*ans)
    else:
      print('No')
  
  else:
    for idx in idxlist:
      if upper == 0:
        ans[idx] = r[idx]
      elif d[idx] >= abs(upper):
        ans[idx] = r[idx]+(-upper)
        upper = 0
      else:
        ans[idx] = l[idx]
        upper -= d[idx]
    if sum(ans) == 0:
      print('Yes')
      print(*ans)
    else:
      print('No')