AtCoder ABC 084 C - Special Trains (4Q, 緑色, 300 点)

Greedy の基本でもある。

• 問題へのリンク

問題概要

駅 があって、駅 から駅 へと、時刻 以降、 秒ごとに発車する列車があって、移動に 秒かかる。他の駅間を移動する列車はない。また、 は の倍数であることが保証される。

各 に対して、駅 を時刻 0 に出発するとき、駅 に到着する時刻の最小値を求めよ。

制約

• 

考えたこと

が小さいので、各 に対する問題を愚直に解いて良さそうである。

さて、次のことに注目しよう。

---

駅 で乗車する時刻が早ければ早いほど、最終的に駅 に到着する時刻も早くなる

---

よって、先の駅のことは考えずに、Greedy に各駅での最速の乗車時刻を求めていけばよい。

具体的に、駅 を時刻 に出発するとき、駅 に辿り着く時刻の最小値を求める関数は、次のように書ける。

    // 駅 i に t 秒後にいるとき、駅 i+1 に最速何秒後に着くか
    auto calc = [&](int i, int t) -> int {
        int min_f_mul = max((t + F[i] - 1) / F[i] * F[i], S[i]);
        return min_f_mul + C[i];
    };

この関数を用いることで、シミュレーションは容易に書ける。

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> C(N-1), S(N-1), F(N-1);
    for (int i = 0; i < N-1; i++) cin >> C[i] >> S[i] >> F[i];

    // 駅 i に t 秒後にいるとき、駅 i+1 に最速何秒後に着くか
    auto calc = [&](int i, int t) -> int {
        int min_f_mul = max((t + F[i] - 1) / F[i] * F[i], S[i]);
        return min_f_mul + C[i];
    };

    for (int i = 0; i < N; i++) {
        int res = 0;
        for (int j = i; j < N-1; j++) {
            res = calc(j, res);
        }
        cout << res << endl;
    }
}