記事の内容

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が答え。

関連記事