AtCoder が提供しているABC（AtCoder Beginner Contest）341 のB問題をC++とPythonで解いてみました。ABC341は、2024年2月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Foreign Exchange（Difficulty : 163）
問題はリンク先をご覧ください。
前から順番に計算して解くことができます。AtCoder Problems による Difficulty は 163 でした。
解答案
国$i$の通貨は、国$(i+1)$の通貨にしか交換できません。このため、国番号が小さい順番に計算することによって、国$N$が持つ通貨数の最大値が分かります。
C++ プログラム例（ABC341B）
a[i] を s[i] で割って切り捨てた解が操作回数になります。これに t[i] を掛けると国$(i+1)$の増える通貨数が分かります。
問題の添え字は1からカウントしていますが、プログラムの添え字は0からカウントしています。最後に a[n-1] を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<ll> s(n - 1);
vector<ll> t(n - 1);
for (int i = 0; i < n - 1; ++i) {
cin >> s[i] >> t[i];
}
for (int i = 0; i < n - 1; ++i) {
a[i + 1] += (a[i] / s[i]) * t[i];
}
cout << a[n - 1] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC341B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 341 B"""
n = int(input())
a = list(map(int, input().split()))
s = [0] * (n - 1)
t = [0] * (n - 1)
for i in range(n - 1):
s[i], t[i] = map(int, input().split())
for i in range(n - 1):
a[i + 1] += (a[i] // s[i]) * t[i]
print(a[n - 1])こちらも「AC」と判定されました。
最後に
最初に問題を読むと複雑に感じました。このため、C問題以降を先に解いていました。戻って問題を読み直すと、前から処理するだけで対応できる問題でした。最初に読むときに、問題の構造に気付ければと思います。
引き続き ABC の問題を紹介していきます。
