Codeforces Round #318 (Div.1) B. Bear and Blocks

問題文

http://codeforces.com/contest/573/problem/B

解法

1ステップ後の h[i] の高さは min(h[i - 1], h[i] - 1, h[i + 1]) になる。
一般化して、k ステップ後の h[i] の高さは min(h[i - k], h[i - k + 1] - 1, ..., h[i] - k, ..., h[i + k]) になる。
逆に考えると、h[i] の高さが 0 になるときは、ある j に対して min(h[i - j] - (k - j)) = 0 (j = -k, ..., k) が成り立つ時なので、k = h[i - j] + j である。
これは、左（と右）から順番に見ていけば求めることができるので、線形で解ける。

問題文

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

int main() {
    int n; cin >> n;
    vector<int> h(n + 2);
    for(int i = 1; i <= n; ++i) {
        cin >> h[i];
    }

    auto calc = [n] (vector<int> hs, bool rev = false) {
        if(rev) reverse(begin(hs), end(hs));
        vector<int> vs(n + 2);
        int mini = 0;
        for(int i = 1; i <= n; ++i) {
            mini++;
            if(mini > hs[i]) mini = hs[i];
            vs[i] = mini;
        }
        if(rev) reverse(begin(vs), end(vs));
        return vs;
    };
    auto left = calc(h), right = calc(h, true);

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, min(left[i], right[i]));
    }

    cout << ans << endl;
}

感想

なんで解けなかったのか、これがわからない。
完全に変なことを考えて泥沼化していた。