はまやんはまやんはまやん

hamayanhamayan's blog

Build Stairs [AtCoder Beginner Contest 136 C]

https://atcoder.jp/contests/abc136/tasks/abc136_c

解説

https://atcoder.jp/contests/abc136/submissions/6734426

単調非減少なので、大きくなっていくようにすればいい。
操作ではマスの高さを下げることしかできないため、前半ほど調整が難しくなっていくと予想できる。
なので、後ろの方からなるべくマスの高さが高くなるようにマスを下げていって、操作が実現できるか試そう。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    rrep(i, N - 2, 0) {
        if (A[i] > A[i + 1] + 1) return no;
        else if (A[i] == A[i + 1] + 1) A[i]--;
    }
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}