記事の内容
2024/7/13に実施されたAtCoderのABC。
そこで出題されたC問題を復習します。
考える過程に学びが多そうだったので、ポイントを振り返っておきたいです。
解法であるPythonコードと考え方をまとめます。
C - Sum = 0
問題
解説
解き方 コード
N=3
L = [3, -4, -2]
R = [5, 1, 3]
この例で挙動を実験してみましょう。解法＝コードは、公式解説を引用しています。
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) #ポイント
print(d)
sumX += d
print(sumX)
X[i] += d
print(X)
print("Yes")
print(*X)
コードの実行結果は以下です。計算過程がわかるように、printを入れています。
2
-1
[5, -4, -2]
1
0
[5, -3, -2]
0
0
[5, -3, -2]
考え方
- 選べる下限としてLをそのまま
Xとする。つまり、Xは現在の仮の答え。 - コードの
#ポイント部では、「今のX_iを増やせる猶予」と「現在の合計値から０までの距離」を比較している。 - もし、「今の
X_iを増やせる猶予」よりも「現在の合計値から０までの距離」が小さい場合、その値分だけX_iを増やすことができる。このとき、このXが答え。 - そうでない場合、「今の
X_iを増やせる猶予」の最大値の分だけ、X_iを増やす。最大値の分だけ増やすのは貪欲法的。最大値を選んでいく方が目標までの距離が小さくなり、最も効率がいいというイメージ。そして、次のX_i+1の検討に託す。 - この操作を繰り返すことにより、いつかは合計値が０になる。そのときの
Xが答え。