AtCoder ABC 123 C - Five Transportations (4Q, 茶色, 300 点)

結構難しい...

問題へのリンク

問題概要

人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。

• 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。移動には 1 秒かかる。

• 都市 2 から都市 3 への移動手段も毎秒ごとに提供されているが、同時に 人しか行けない。移動には 1 秒かかる。

• 都市 3 から都市 4 への移動手段も毎秒ごとに提供されているが、同時に 人しか行けない。移動には 1 秒かかる。

• 都市 4 から都市 5 への移動手段も毎秒ごとに提供されているが、同時に 人しか行けない。移動には 1 秒かかる。

• 都市 5 から都市 6 への移動手段も毎秒ごとに提供されているが、同時に 人しか行けない。移動には 1 秒かかる。

全員が都市 6 まで行くのに要する時間を求めよ。

制約

• 

考えたこと

えっ...！！！！！！難しい！！！！！！！！
愚直シミュレーションでは間に合わない。なにかまとめて状態遷移させたりとかの工夫が必要になる。でもそんなことしたくない。

何かいい感じの楽できる構造を見つけ出したい。例えば の場合を考えてみよう。 くらいで。このとき、実際にシミュレーションしてみると

• 「定員 2 人」の手前で人が詰まる
• 「定員 2 人」のところは、最初に人が来てからはずっと常に 2 人ずつ満員を乗せていく感じになる

ということがわかる。より一般に、定員の人数が最も小さいところがボトルエックになる。そして

1. 最初の人がボトルネックに到達するまで
2. ボトルネックを 人分裁くまで
3. 最後にボトルネックが通過した人がゴールするまで

を足したものが答えになるわけだ。1 と 3 は実は合計して必ず 4 になる。ちょっと色々試してみるとわかる。

2 は、ボトルネックの定員を 人して、 を を割って余りを切り上げた値になる。その値は になる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long N; cin >> N;
    vector<long long> A(5);
    long long mi = 1LL<<60;
    for (int i = 0; i < 5; ++i) cin >> A[i], mi = min(mi, A[i]);
    cout << (N + mi - 1) / mi + 4 << endl;
}