ABC-60 C 解いて見た - xlkeiの日記

なかなかAtCoderのCDの完答率が安定しないのでCD問題を解いた時の考え方やそのほかをまとめていきます。

では以下問題

ABC-60 C

Sentou

問題文

とある銭湯には、スイッチを押すと $T$ 秒間お湯が出るシャワーがあります。

なお、お湯が出ているときにスイッチを押すと、そのタイミングから $T$ 秒間お湯が出つづけます。お湯の出る時間が $T$ 秒間延長されるわけではないことに注意してください。

このシャワーの前を、 $N$ 人の人がスイッチを押して通り過ぎていきます。 $i$ 人目の人は、 $1$ 人目の人がスイッチを押した $t_{i}$ 秒後にスイッチを押します。

お湯が出る時間の総和は何秒かを求めてください。

制約

$1 ≦ N ≦ 200, 000$
$1 ≦ T ≦ 10^{9}$
$0 = t_{1} < t_{2} < t_{3} <, . . ., < t_{N - 1} < t_{N} ≦ 10^{9}$
$T, t_{i}$ はすべて整数である

考えたこと

最初にシャワーが出ている時間にボタンが押されない場合の最大の時間を求めて、そのあとボタンが押されている時間に押された時間分の差分を算出し最大の時間との差分を取れば良い

フローは以下のように考えました

- 入力の受け取り

- その入力からシャワーが最大で出る時間を算出する(N × T)

- それぞれ ti にアクセスしながら以下の処理をする

- もし最後の要素ではなく今の時間(ti)と次の時間(ti + 1)の差分がT未満の時

- 最大の時間からシャワーの時間と時間(ti)と次の時間(ti + 1)の差分をとる

- 最大の時間を出力する

ソースコード

>|cpp|
#include <iostream>
#include <vector>
using namespace std;

int main(void){
    int N,T;
    int max;
    vector<unsigned long> ti(N);
    max = N * T;
    for(int i = 0; i < N; i++){
        cin >> ti[i];
    }
    for(int i = 0; i < N; i++){
        if (i != N - 1 && ti[i + 1] - ti[i] < T){
             max = max - (T - (ti[i + 1] - ti[i]));
        }
    }
    cout << max << endl;
}

こんな感じでAC取れました。