AtCoder Beginner Contest 060 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Beginner Contest 060 C ( ABC 060 C ) 。
簡単めの問題だったので特に苦労せず解けて良かった。
今日の一問はSentou！前回の問題が難しかったから今日は簡単めで。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月25日
こういうのって明確に「アルゴリズム」って言われるほどのものじゃないけど、苦戦する人もいるし、さらっと組めて欲しい、って感じの問題。そんなんばっか選んでる気がする！#chokudai今日の一問https://t.co/nmlTh7JDkj
C - Sentou
スイッチを押してからT秒間お湯が出るシャワーがある。
シャワーが出ている間にスイッチが押された場合は、押した瞬間からT秒間出る。
ti秒にスイッチが押されるので、 合計で何秒間シャワーが出ていたかを求めよ。
解いた方針
問題文で強調されている通り、 スイッチが押されるタイミングには、
- (1) シャワーが出ている場合
- (2) シャワーが出ていない場合
の二通りが考えられる。
この二通りについて上手く考えられれば解けそうだなということは分かる。
まず、t[i] にスイッチが押される。
すると T 秒間お湯が出続ける。
この t[i] から t[i] + T までにスイッチが押された場合(1)と押されなかった場合(2)を考えればよい。
（つまりシャワーが出ている間にスイッチが押されるか押されないかを考えることにした）。
t[i] から t[i] + T までにスイッチが押されないのであれば T だけお湯は出続ける。
スイッチが押された場合は押されるまでお湯が出たとして、 次の t[i+1] に移行する。
この処理はお湯が出ていた時間をカウントする変数をcntとして
cnt += min(T, t[i+1]-t[i])
というように実装できる。
コード
解説を読んで書き直した。
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ll N, T; cin >> N >> T;
vector<ll> t(N+1, INF);
for(int i = 0; i < N; i++) cin >> t[i];
ll time = 0;
for(int i = 0; i < N; i++) {
time += min(T, t[i+1] - t[i]);
}
cout << time << endl;
return 0;
}
おわりに
ちょうどいい問題だった。
