ABC319 E問題（Bus Stops）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）319 のE問題をC++とPythonで解いてみました。ABC319は、2023年9月9日21:00に実施されました。

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

E問題 Bus Stops（Difficulty : 1353）

問題はリンク先をご覧ください。

ABC319 E問題 Bus Stops

求める到着時刻の一部に周期性があり、それを使って解くことができました。AtCoder Problems による Difficulty は 1353 でした。

解答案

$P_1 = 2, \; P_2 = 3$ の場合

$X = 0, \; Y = 0,\; T_1 = 1, \; T_2 = 1$ として、到着する時刻を計算してみます。周期性を見るために、少し長いですが開始時間を 0 から 18 まで計算しました。

2024/4/30 表に誤記を修正しました。

この場合は、$0 \leqq i < 6$ の範囲の出発時刻について、その到着時刻 $f(i)$ を計算しておけば、それ以降の任意の出発時刻 $i$ の到着時刻は以下となります。

$$(i / 6) \times 6 + f (i \,\%\, 6)$$

この6は、2と3の最小公倍数になります。「それぞれのバス停では2の倍数時刻、または3の倍数時刻まで待つため、2と3の最小公倍数である6が周期となる」と（厳密ではないですが）説明できます。

結論

この問題では、それぞれのバス停で1から8の倍数時刻まで待つ可能性があります。上の実験から、{1, 2, 3, 4, 5, 6, 7, 8} の最小公倍数840 (= 2 × 2 × 2 × 3 × 5 × 7) の周期を持つことが予想できます。実際にこれは正しいです。厳密な証明は公式解説で説明されています。

C++ プログラム例（ABC319E）

上で考察したように $0 \leqq i < 840$ の範囲の出発時刻について、その到着時刻 $f(i)$ を計算しておけば、すべての場合に $O(1)$ で到着時刻を求めることができます（32、33行目）。

各バス停の出発時刻を求めるために a / b を切り上げた結果が必要ですが、これは条件分岐を使わなくても (a + b – 1) / b で求めることができます（22行目）。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	int n;
	ull x, y;
	cin >> n >> x >> y;
	vector<int> p(n);
	vector<ull> t(n);
	for (int i = 0; i < n - 1; ++i) {
		cin >> p[i] >> t[i];
	}

	const int L = 2 * 2 * 2 * 3 * 5 * 7;
	vector<ull> f(L, 0);
	for (int i = 0; i < L; ++i) {
		f[i] = i + x;
		for (int j = 0; j < n - 1; ++j) {
			f[i] = ((f[i] + p[j] - 1) / p[j]) * p[j] + t[j];
		}
		f[i] += y;
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		ull qt, result;
		cin >> qt;
		result = (qt / L) * L;
		result += f[qt % L];
		cout << result << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC319E）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 319 E"""
n, x, y = map(int, input().split())
p = [0] * (n - 1)
t = [0] * (n - 1)
for i in range(n - 1):
    p[i], t[i] = map(int, input().split())

L = 2 * 2 * 2 * 3 * 5 * 7
f = [0] * L
for i in range(L):
    f[i] = i + x
    for j in range(n - 1):
        f[i] = ((f[i] + p[j] - 1) // p[j]) * p[j] + t[j]
    f[i] += y

q = int(input())
for i in range(q):
    qt = int(input())
    result = (qt // L) * L
    result += f[qt % L]
    print(result)

こちらも「AC」と判定されました。

最後に

この問題は、時間切れで取り組むことができませんでした。公式解説の理解に基づいて書いたプログラムを紹介しました。この難易度の問題が解けると非常にうれしく感じると思います。

引き続き ABC の問題を紹介していきます。