けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

結構難しい...

問題へのリンク

問題概要

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

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

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

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

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

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

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

制約

  •  1 \le N, A, B, C, D, E \le 10^{15}

考えたこと

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

何かいい感じの楽できる構造を見つけ出したい。例えば  (A, B, C, D, E) = (5, 3, 4, 2, 6) の場合を考えてみよう。 N = 100 くらいで。このとき、実際にシミュレーションしてみると

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

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

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

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

2 は、ボトルネックの定員を  mi 人して、 N mi を割って余りを切り上げた値になる。その値は  (N + mi - 1) / mi になる。

#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;
}