AtCoder が提供しているABC（AtCoder Beginner Contest）339 のC問題をC++とPythonで解いてみました。ABC339は、2024年2月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Perfect Bus（Difficulty : 174）
問題はリンク先をご覧ください。
累積和の最小値を求めます。AtCoder Problems による Difficulty は 174 でした。
解答案
累積和の最小値が負の値であれば、それを0にするように乗客を乗せれば、バスの運行中、常に0人以上の乗客が乗っており矛盾しません。
C++ プログラム例（ABC339C）
累積和の最小値を変数 min_a に格納します。min_a が負の値であれば、それにー1を掛けた値を乗客の初期値とします。最後に乗っている乗客（更新後の変数 sum の値）を加えて出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ll min_a = INF;
ll sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
min_a = min(min_a, sum);
}
ll init = 0;
if (min_a < 0){
init = -min_a;
}
cout << init + sum << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC339C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 339 C"""
INF = (1 << 60)
n = int(input())
a = list(map(int, input().split()))
min_a = INF
s = 0
for i in range(n):
s += a[i]
min_a = min(min_a, s)
init = 0
if min_a < 0:
init = -min_a
print(init + s)こちらも「AC」と判定されました。
最後に
累積和の最小値を求めることに気付けば、解きやすい問題でした。
引き続き ABC の問題を紹介していきます。
