【AtCoder】ABC 446 C - Omelette Restaurant

C - Omelette Restaurant

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 384 / NoviSteps: 3Q / 配点: 300 点

問題概要

AtCoder レストランは開店してから $N$ 日間営業した。
開店してから $i$ 日目 には次の行動が行われた。

• $i$ 日目の朝に、$A_i$ 個の卵を仕入れる。
• $i$ 日目の昼に、$B_i$ 個の卵を使用する。このとき、卵は 在庫にある卵の中で仕入れた順に使用される 。
• $i$ 日目の夜に、仕入れてから $D$ 日間以上経過した卵をすべて処分する。

$N$ 日目の夜の行動の後で、レストランに何個の卵が残っているか求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

• $1 \leq T\leq 2\times 10^5$
• $1 \leq D \leq N \leq 2\times 10^5$
• $1 \leq A_i,B_i \leq 10$
• $N$ 日間のそれぞれの昼において、卵が足りなくなることはない。
• それぞれの入力において、各テストケースにおける $N$ の総和は $2\times 10^5$ 以下である。
• 入力はすべて整数

考察

$A_i, B_i$ の制約が小さいことから卵の総数はそこまで多くはならないことが分かるので、シミュレーションで解くことを考える。

卵を仕入れた日をqueueを使って管理することを考えると、 $i$ 日目の行動はそれぞれ次のように実装できる。

• 朝: queue に $A_i$ 個の要素 $i$ を追加する。
• 昼: queue の先頭から $B_i$ 個の要素を削除する。
• 夜: queue の先頭から、 $i - D$ 以下の要素をすべて削除する。

これを $N$ 日目まで繰り返した後の queue の大きさが答えとなる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int solve()
9.{
10.    int N, D;
11.    cin >> N >> D;
12.    vector<int> A(N), B(N);
13.    rep(i, 0, N) cin >> A[i];
14.    rep(i, 0, N) cin >> B[i];
15. 
16.    queue<int> que;
17.    rep(i, 0, N)
18.    {
19.        rep(j, 0, A[i]) que.push(i);
20.        rep(j, 0, B[i]) que.pop();
21.        while (!que.empty() && que.front() <= i - D)
22.            que.pop();
23.    }
24. 
25.    return que.size();
26.}
27. 
28.int main()
29.{
30.    int T;
31.    cin >> T;
32. 
33.    while (T--)
34.    {
35.        cout << solve() << endl;
36.    }
37. 
38.    return 0;
39.}

https://atcoder.jp/contests/abc446/submissions/73788592

atcoder.jp

実装時間: 10 分

コメント

A_i, B_i$ の制約が小さいので、素直なシミュレーションで解くことができる問題だった。