AtCoder が提供しているABC（AtCoder Beginner Contest）362 C問題をC++とPythonで解いてみました。ABC362は、2024年7月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sum = 0（Difficulty : 521）
問題の詳細は、リンク先をご覧ください。
初期値を最小値として、各要素を可能な限り増やしていきます。AtCoder Problems による Difficulty は 521 でした。
解答案
$\sum L_i > 0$ であれば、明らかに解はありません。同じように $\sum R_i < 0$ である場合も解はありません。
$\sum L_i \leqq 0 \leqq \sum R_i$ であることを前提とします。この場合、$X_i$ の初期値を $L_i$ とします。初期値では、$\sum X_i$ は 0 以下となります。それぞれの $X_i$ について、$\sum X_i$ が 0 になるまで値を増やします。それぞれの要素は、$R_i – L_i$ より値が増やせないことに注意します。
C++ プログラム例（ABC362C）
上記の考察をプログラムに変換します。
- L[i]の総和が0を超えている、またはR[i]の総和が0未満の場合は、”No” を出力して終了します。
- “Yes” を出力した後、配列 result の初期値を L にする。L の総和を remain とする（30ー32行目）。
- result[i] に -remain を加える。ただし、R[i] – L[i] を上限とする。
- remain を更新する。
- 最後に result を出力します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> L(n);
vector<ll> R(n);
ll sum_L = 0;
ll sum_R = 0;
for (int i = 0; i < n; ++i) {
cin >> L[i] >> R[i];
sum_L += L[i];
sum_R += R[i];
}
if ((0 < sum_L)||(sum_R < 0)) {
cout << "No" << endl;
return 0;
} else {
cout << "Yes" << endl;
}
ll remain = sum_L;
vector<ll> result = L;
for (int i = 0; i < n; ++i) {
ll d = min(R[i] - L[i], -remain);
result[i] += d;
remain += d;
}
for (int i = 0; i < n; ++i) {
cout << result[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC362C）
Python版も基本的な考え方は同じです。プログラムを途中で終了するために sys.exit を呼び出しています。以下がプログラムです。
"""AtCoder Beginner Contest 352 C"""
import sys
n = int(input())
L = [0] * n
R = [0] * n
for i in range(n):
L[i], R[i] = map(int, input().split())
sum_L = sum(L)
sum_R = sum(R)
if 0 < sum_L or sum_R < 0:
print("No")
sys.exit()
else:
print("Yes")
remain = sum_L
result = L.copy()
for i in range(n):
d = min(R[i] - L[i], -remain)
result[i] += d
remain += d
print(*result)こちらも「AC」と判定されました。
最後に
この問題は、1時間程度考えましたが、結果的に解くことができませんでした。貪欲法に近いことを考えていましたが、いろいろ考えすぎていました。
引き続き ABC の問題を紹介していきます。
