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

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

AtCoder AGC 011 A - Airport Bus (300 点)

頭の整理がちょっと大変な問題

問題へのリンク

問題概要

 N 人が次々とバス停に到着する ( N 人の到着時刻が  T_1, T_2, \dots, T_N で与えられる)。以下の条件を満たすように乗客たちをバスに乗せていきたい。

  • どの乗客もバス停に到着してから  K 分以内に出発させる
  • 1 台のバスには  C 人までしか乗せられない

最小の何台のバスで全員を乗せることができるか求めよ。

制約

  •  2 \le N \le 10^{5}

考えたこと

問題で問われている状況を整理することが求められる。こういうのはまずは、色々な状況を想定してみるのがよいと思う。例えば...

  •  N = 100, K = 10, C = 10 として最初の人が到着してから全員が  10 分以内に来るとしてもバス定員は  10 人なので、 100 人を運ぶには  10 台のバスが必要になる。

  •  N = 100, C = 100 でバス定員に余裕があっても、  K = 10 で全員が 100 分起きに来るとしたら、1 人ずつしか乗せられないので  100 台のバスが必要になる。

こうしてみると、どちらの条件もよく効いてくることがわかる。しかしながら言えることは


先に到着した人を待たせてまで、後の人を先に乗せるメリットはまったくない


ということ。これは今回の問題では半ば当たり前だけど、今後より難しい問題で Greedy の考察をするときに大変重要になって来る考え方でもある。

解法を整理すると、

  • 現在発車待ちのバスに、以下のいずれかの状態になるまでは、「来た人を乗せる」を繰り返す
    • 最初に人が乗ってから  K 分経つ
    • 乗客が  C 人になる
  • 以上の状態になったら発車させて、その次の人が到着したと同時に新しいバスを開く

という風にすればよい。実装は

drken1215.hatenablog.com

に書いたような考え方でできる。

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

int main() {
    int N, C, K; cin >> N >> C >> K;
    vector<int> T(N);
    for (int i = 0; i < N; ++i) cin >> T[i];
    sort(T.begin(), T.end());
    int res = 0;
    for (int i = 0; i < N;) {
        ++res;
        int start = i;
        while (i < N && T[i] - T[start] <= K && i - start < C) ++i;
    }
    cout << res << endl;
}