yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

B - AtCoder Amusement Park / AtCoder Beginner Contest 353

ABC353 AtCoder C++ AtCoder Beginner Contest 200点 競技プログラミング

問題

遊園地に k 人乗りのアトラクションがあり、このアトラクションの待機列に n 個のグループが並んでいる。 このグループに対して、次の手順で誘導を行う。

  1. 待機列に並んでいるグループがない場合、誘導を終了する。
  2. アトラクションの空席数と待機列の先頭のグループの人数を比較して、
    • アトラクションの空席数の方が少ないとき、アトラクションを出発させる。その後、アトラクションの空席数は k となる。
    • そうでないとき、先頭のグループの全員をアトラクションに入れる。空席数は先頭のグループの人数分だけ減少する。
  3. 1.に戻る。

以上の手順で誘導を行うとき、アトラクションを出発させる回数を求めよ。

入力

まず最初の1行目に、整数 n, \, k が与えられる。

次の1行に、 n 個の整数 {a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n} が順に与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 100
  • 1 \leq k \leq 100
  • 1 \leq {a}_{i} \leq k

出力

答えを1行で出力すること。

解法

各グループについて順番に人数を見ていき、アトラクションに乗せていくシミュレーションを行うことを考えます。 具体的には、現時点でアトラクションに乗っている人数を \mathrm{sum} 、アトラクションを出発させた回数を \mathrm{ans} とするとき、 i = 1, \, \cdots , \, n の順に、

  • \matrm{sum} + {a}_{i} \leq k であれば i 番目のグループも乗せるため、 \mathrm{sum} \leftarrow \mathrm{sum} + {a}_{i} とする。
  • \mathrm{sum} + {a}_{i} \gt k であればアトラクションを出発させるため、 \mathrm{ans} \leftarrow \mathrm{ans} + 1 とし、 \matrm{sum} \leftarrow {a}_{i} とする。

という更新を行っていきます。

このとき、 n 番目のグループについての更新が終わったあと、 \mathrm{sum} \gt 0 であれば、最後のグループを含んだ組がまだ出発していないことになるため、 \mathrm{ans} \leftarrow \mathrm{ans} + 1 と更新することが必要となります。

この手順で最終的に得られる \mathrm{ans} の値が答えとなるので、この値を出力すれば、この問題は解けたということになります。

計算量については、 n 個のグループを順に見ていることから O(n) であると言え、これは十分実行時間制限に間に合います。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

int n, k, a[105];
int sum = 0, ans = 0;

int main() {
  // 値の入力
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];

    if (sum + a[i] > k) {
      // もし定員オーバーするなら、ansを1増やし、次のアトラクションに乗せる
      ans++;
      sum = a[i];
    } else {
     // そうでないならば、グループ i をアトラクションに乗せる
      sum += a[i];
    }
  }
  // 最後の出発についての確認を行う
  if (sum > 0) {
    ans++;
  }
  // 答えの出力
  cout << ans << endl;

  return 0;
}