【AtCoder】ABC 480 C - Self-Stopping Shower

2026-10-20

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/茶Diff AtCoder/NoviSteps/2Q AtCoder/イベントソート AtCoder/重複区間のmerge 競技プログラミング

C - Self-Stopping Shower

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

AtCoder

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

問題概要

あるシャワーでは、時刻 $t$ にボタンを押すと時刻 $t$ から時刻 $t+K$ までの $K$ 秒間お湯が出る。お湯が出ているときに再びボタンを押した場合も、最後にボタンを押した時刻から $K$ 秒間お湯が出る。

$N$ 人の青木君がいて、 $i$ 人目の青木君は時刻 $A_i$ にボタンを $1$ 回押す。

時刻 $0$ から時刻 $T$ までの間に常にお湯が出ているようにするために、高橋君は最小で何回ボタンを押す必要があるかを求めよ。ただし、ボタンを押したタイミングと最後にボタンを押してからちょうど $K$ 秒経ったタイミングはいずれもお湯が出ているものとする。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10^9$
$1 \leq T \leq 10^9$
$0 \leq A_i \leq 10^9$
入力される値はすべて整数

考察

お湯が出ている時間を区間として考え、重なる区間をmergeする。

その後、区間 $[0, T]$ でまだ覆われていない区間の長さをそれぞれ $d$ とすれば、その区間に対して $\left\lceil \frac{d}{K} \right\rceil$ 回ボタンを押す必要がある。

これをすべての区間に対して行い、合計すればよい。

実装では、まず $A_i$ の昇順にソートし、これまでの区間の右端を $r$ として、次の区間の左端が $r$ より大きい場合にボタンを押す回数を計算するように処理すればよい。

入力では $A_i$ がソートされていないことと、 $\max A_i > T$ の場合があることに注意すること。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8. 
9.template <class T1, class T2>
10.inline auto div_ceil(T1 a, T2 b)
11.{
12.    if (b < 0)
13.        a *= -1, b *= -1;
14.    if (a <= 0)
15.        return a / b;
16.    else
17.        return (a - 1) / b + 1;
18.}
19.template <typename T>
20.inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
21. 
22.// ======================================== //
23. 
24.int main()
25.{
26.    int N;
27.    ll K, T;
28.    cin >> N >> K >> T;
29.    vector<ll> A(N);
30.    rep(i, 0, N) cin >> A[i];
31. 
32.    sort(all(A));
33. 
34.    ll right = 0;
35.    int ans = 0;
36.    rep(i, 0, N) {
37.        if (A[i] > T) break;
38. 
39.        if (A[i] > right) {
40.            ans += div_ceil(A[i] - right, K);
41.        }
42. 
43.        chmax(right, A[i] + K);
44.    }
45. 
46.    if (right < T) {
47.        ans += div_ceil(T - right, K);
48.    }
49. 
50.    cout << ans << endl;
51. 
52.    return 0;
53.}