AtCoder ABC 383 A - Humidifier 1 (6Q, 灰色, 150 点)

これ 150 点なのは解釈一致だし、難しいと思うけど、Difficulty が 19 とすごく低いのが驚き！

• 問題へのリンク

問題概要

今、時刻 0 で水は 0 L たまっている。

これから時刻 にそれぞれ水が L 注がれる。

なお、水が 1 L 以上あるとき、時刻が 1 経過するごとに水が 1 L 減少する。

時刻 の水量を求めよ。

考えたこと

時刻 からスタートしよう。つまり、水が L ある状態からスタートする。このとき、 について、次のように考えれば良い。なお、水量を res とする。

• 前回の給水から今回までに、水は need = T[i] - T[i-1] だけ、なくなっているはずである
• よって、水の量は res - need になるはずである
• ただし、水量が 0 未満にはならないことから、最終的な水量は max(res - need, 0) となる
  • つまり、res = max(res- need, 0) と更新すればよい
• その後、res に V[i] を足す

この一連の操作は for 文で実装できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> T(N), V(N);
    for (int i = 0; i < N; i++) cin >> T[i] >> V[i];

    int res = V[0];  // T[0] からスタート
    for (int i = 1; i < N; i++) {
        int need = T[i] - T[i-1];  // 前回の給水から無くなる水量
        res = max(res - need, 0);  // res から need を引くが、0 より小さくはならない

        // 給水
        res += V[i];
    }
    cout << res << endl;
}