AtCoder

ABC378 B問題(Garbage Collection)を解く

AtCoder_ABC378_B

AtCoder が提供しているABC(AtCoder Beginner Contest)378 B問題をC++とPythonで解いてみました。ABC378は、2024年11月2日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Garbage Collection(Difficulty : 118)

問題の詳細は、リンク先をご覧ください。

ABC378 B問題 Garbage Collection

日常のゴミ捨てを思い出しました。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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA