B. Maximums (Codeforces Global Round 7)

問題

https://codeforces.com/contest/1326/problem/B

問題概要

非負整数からなる数列がある。また、1からnまでのそれぞれについてをと定義する。ここでのときであることに注意する。

例えばのときである。

ここで任意のについてをと定義する。

例えば上記の配列とに対してはでありとなる。

さて、配列が与えられるので、配列を復元せよ。

考察

なので移項してです。ここでであることはわかっているので、実はです。まずがわかりました。

ですので、がわかるともわかります。するとなのでがわかります。

というように、この問題は端から順に単純な計算で解決できるのでした。

実装上の工夫として計算したmaxを保存しておくとよいでしょう。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];
    a[0] = b[0];
    a[1] = b[0] + b[1];
    int mx = max(a[0], a[1]);
    for (int i = 2; i < n; i++) {
        a[i] = mx + b[i];
        mx = max(mx, a[i]);
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << (i == n - 1 ? '\n' : ' ');
    }
}

反省

max(a[0], a[1])と書いていたつもりが、(a[0], a[1])と書いていたことに気づかず2WA・・・。なんともったいない。でもこれでもpretest 7まで行ってしまうのはどうかと思う・・・。こどふぉのpretest本当にあてにならないです。