AtCoderログ：0125 - AGC 011 A

問題

問題文

高橋空港には，毎日飛行機で $N$ 人の乗客が到着します．$i$ 番目の乗客は時刻 $T_i$ に到着します．
高橋空港に到着する乗客は全員バスで市内へ移動します．どのバスも定員は $C$ 人であり，$C$ 人以下の乗客を乗せることができます．飛行機の乗客は，飛行機の到着時刻よりも早く出発するバスには乗ることができません．また，飛行機の到着時刻から $K$ の時間が経過した後にもバスに乗れていないと，怒り出してしまいます． そのため，$i$ 番目の乗客は，出発時刻が $T_i$​ 以上 $T_i+K$ 以下であるようなバスに乗れるようにしないといけません．
この条件のもとで，うまくバスの出発時刻を定めるとき，必要なバスの数の最小値を求めてください．ただし，バスの出発時刻は必ずしも整数である必要はなく，同じ時刻に出発するバスが複数あってもかまいません．

制約

・$2 \le N \le 100000$
・$1 \le C \le 10^9$
・$1 \lw K \le 10^9$
? ・$1 \le T_i \le 10^9$
・$C,K,T_i$ は整数

収録されている問題セット

• [精] AtCoder に登録したら次にやること 第09問類題

回答

回答1 (AC)

バスの受付になったつもりで考えるとわかりやすいでしょう。すると乗客の到着時刻は時刻順になっていて欲しいと思うのは当然で、そう仮定します。実際、到着時刻をソートすることでこの仮定は簡単にクリヤできます。受付は、最初の乗客の到着時刻 $T$ をチェックし、到着時刻が $T+K$ 以内の乗客をバスに乗せていきます。ただし途中でバスの乗客者数が $C$ 人になった場合にはそこで打ち切り、バスを発車させた後、残った乗客の先頭の到着時刻をチェックするところから繰り返します。また、途中で到着時刻が $T+K$ 以内の乗客がいなくなった場合もバスを発車させ、その後に残った乗客の先頭の到着時刻をチェックするところから繰り返します。これらの繰り返しによって、全員の乗客をバスに乗せることができます。計算量を調べると、ソートに $O(N log N)$、バスへの割り振りに $O(N)$ が必要ですが、$N \le 10^6$ よりこれらは処理可能です。コードは以下のようになりました。

agc011a-1.cpp

# include <bits/stdc++.h>
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.at(i);
  }
  sort(t.begin(),t.end());
  
  int index = 0, pnumber = 0, bnumber = 0;
  while ( index<n ) {
    int tk = t.at(index)+k;
    while ( index<n && t.at(index)<=tk ) {
      pnumber += 1;
      index += 1;
      if ( pnumber%c==0 ) {
        bnumber += 1;
        pnumber =  0;
        break;
      }
    }
    if ( pnumber>0 ) {
      bnumber += 1;
      pnumber =  0;
    }
  }
  
  cout << bnumber << endl;
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0124 - ABC 158 B