ABC480 C - Self-Stopping Shower
- サイト
- AtCoder
- コンテスト
- ABC480
- 問題
- C - Self-Stopping Shower
- 難易度
- 625
シャワーのボタンを時刻 に押すと、時刻 から までお湯が出ます(お湯が出ている間に押した場合も、最後に押した時刻から 秒間出ます)。 人の青木君が、それぞれ時刻 にボタンを押します。時刻 から までずっとお湯が出ているようにするために、高橋君がボタンを押す回数の最小値を求める問題です(、、)。
お湯が出ている時刻は、誰かがボタンを押した時刻 についての区間 の和集合です。したがってこの問題は、青木君の区間 に長さ の区間をいくつか足して、 を覆うときの、足す区間の個数の最小値を求める問題になります。
青木君の区間だけでは覆われない部分は、いくつかのすき間に分かれます。すき間の長さが なら、長さ の区間は少なくとも 個必要で、すき間の左端から ずつずらして置けばちょうどその個数で覆えます。また、1 つの区間が 2 つのすき間にまたがることはありません。2 つのすき間の間には青木君の区間が丸ごと入っていて、またぐには長さが より大きくなければならないからです。よって、すき間ごとの の和が答えです。
すき間は、青木君の押す時刻を小さい順に見ていけば求められます。今までの区間で覆われている右端を とします(はじめは です)。次の時刻 が なら、 から までの長さ のすき間があります。最後に、 を時刻の列に加えておくと、 までに残ったすき間も同じように扱えます。 以上の時刻に押される分は を覆うのに関係ないので、取り除いておきます。
計算量はソートがいちばん重く、 です。
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 は、 と、 より前の青木君の時刻を並べてソートした列です。p が今まで覆えている右端で、b の前にすき間があれば ceildiv(b - p, K)()回押します。そのあと b に押された分で、右端は b + K まで伸びます。 の青木君がいないときは、最初のすき間に時刻 も含まれるので、高橋君が時刻 に押すことになります。
使用ライブラリ:cpp_include@9c33ee7