AtCoder が提供しているABC（AtCoder Beginner Contest）378 B問題をC++とPythonで解いてみました。ABC378は、2024年11月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Garbage Collection（Difficulty : 118）
問題の詳細は、リンク先をご覧ください。
日常のゴミ捨てを思い出しました。AtCoder Problems による Difficulty は 118 でした。
解答案
C++ プログラム例（ABC378B）
例として、$q_i = 7, r_i = 3$ とします。また月曜日からカウントするとします。ゴミは毎週3日目（水曜日）に収集されることを意味します。
- 例1）$d_i = 9$ であれば、火曜日にゴミを出すので、翌日の水曜日（10日目）に収集されます。
- 例2）$d_i = 11$ であれば、木曜日にゴミを出すので、翌週の水曜日（17日目）に収集されます。
その週に間に合うか判断し、間に合わない場合は、7（$q_i$）を加えます。これをプログラムとして実装したのが、以下となります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> q(n), r(n);
for (int i = 0; i < n; ++i) {
cin >> q[i] >> r[i];
}
int query;
cin >> query;
for (int i = 0; i < query; ++i) {
int t, d;
cin >> t >> d;
--t;
int diff = d - d / q[t] * q[t];
if (diff <= r[t]) {
cout << d / q[t] * q[t] + r[t] << endl;
} else {
cout << d / q[t] * q[t] + r[t] + q[t] << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC378B）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 378 B"""
n = int(input())
q = [0] * n
r = [0] * n
for i in range(n):
q[i], r[i] = map(int, input().split())
query = int(input())
for i in range(query):
t, d = map(int, input().split())
t -= 1
diff = d - d // q[t] * q[t]
if diff <= r[t]:
print(d // q[t] * q[t] + r[t])
else:
print(d // q[t] * q[t] + r[t] + q[t])こちらも「AC」と判定されました。
最後に
日常のゴミ捨ての問題として考えることができました。
引き続き ABC の問題を紹介していきます。
