AtCoder が提供しているABC（AtCoder Beginner Contest）353 のB問題をC++とPythonで解いてみました。ABC353は、2024年5月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 AtCoder Amusement Park（Difficulty : 51）
問題はリンク先をご覧ください。
ABC353 B問題 AtCoder Amusement Park
貪欲法でシミュレーションします。AtCoder Problems による Difficulty は 51 でした。
解答案
C++ プログラム例（ABC353B）
アトラクションの空き（変数 space）が待っている先頭のグループの人数以上であれば、詰められるだけ詰めます。
アトラクションの空きが待っている先頭のグループの人数より少なくなれば、アトラクションをスタートします。
注意としては、while 文の最後に詰めたアトラクションは、まだスタートしていないため、ループ後にスタートさせます（26行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int result = 0;
int index = 0;
int space = k;
while (index < n) {
if (space >= a[index]) {
space -= a[index];
++index;
} else {
++result;
space = k;
}
}
++result;
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC353B）
基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 353 B"""
n, k = map(int, input().split())
a = list(map(int, input().split()))
result = 0
index = 0
space = k
while index < n:
if space >= a[index]:
space -= a[index]
index += 1
else:
result += 1
space = k
result += 1
print(result)こちらも「AC」と判定されました。
最後に
この難易度の問題は、速く解けるようになりたいです。
引き続き ABC の問題を紹介していきます。
