コンテンツにスキップ

ABC480 C - Self-Stopping Shower

サイト
AtCoder
コンテスト
ABC480
問題
C - Self-Stopping Shower
難易度
625

シャワーのボタンを時刻 tt に押すと、時刻 tt から t+Kt + K までお湯が出ます(お湯が出ている間に押した場合も、最後に押した時刻から KK 秒間出ます)。NN 人の青木君が、それぞれ時刻 AiA_i にボタンを押します。時刻 00 から TT までずっとお湯が出ているようにするために、高橋君がボタンを押す回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、1≤K,T≤1091 \le K, T \le 10^9、0≤Ai≤1090 \le A_i \le 10^9)。

お湯が出ている時刻は、誰かがボタンを押した時刻 tt についての区間 [t,t+K][t, t + K] の和集合です。したがってこの問題は、青木君の区間 [Ai,Ai+K][A_i, A_i + K] に長さ KK の区間をいくつか足して、[0,T][0, T] を覆うときの、足す区間の個数の最小値を求める問題になります。

青木君の区間だけでは覆われない部分は、いくつかのすき間に分かれます。すき間の長さが gg なら、長さ KK の区間は少なくとも ⌈g/K⌉\lceil g / K \rceil 個必要で、すき間の左端から KK ずつずらして置けばちょうどその個数で覆えます。また、1 つの区間が 2 つのすき間にまたがることはありません。2 つのすき間の間には青木君の区間が丸ごと入っていて、またぐには長さが KK より大きくなければならないからです。よって、すき間ごとの ⌈g/K⌉\lceil g / K \rceil の和が答えです。

すき間は、青木君の押す時刻を小さい順に見ていけば求められます。今までの区間で覆われている右端を pp とします(はじめは p=0p = 0 です)。次の時刻 bb が p<bp < b なら、pp から bb までの長さ b−pb - p のすき間があります。最後に、TT を時刻の列に加えておくと、TT までに残ったすき間も同じように扱えます。TT 以上の時刻に押される分は [0,T][0, T] を覆うのに関係ないので、取り除いておきます。

計算量はソートがいちばん重く、O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, K, T);
VL(A, N);
vl B = {T};
for (ll a : A)
if (a < T)
B.push_back(a);
sort(B);
ll ans = 0, p = 0;
for (ll b : B) {
if (p < b)
ans += ceildiv(b - p, K);
chmax(p, b + K);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

B は、TT と、TT より前の青木君の時刻を並べてソートした列です。p が今まで覆えている右端で、b の前にすき間があれば ceildiv(b - p, K)(⌈(b−p)/K⌉\lceil (b - p) / K \rceil)回押します。そのあと b に押された分で、右端は b + K まで伸びます。Ai=0A_i = 0 の青木君がいないときは、最初のすき間に時刻 00 も含まれるので、高橋君が時刻 00 に押すことになります。

使用ライブラリ:cpp_include@9c33ee7