トランポリン [パソコン甲子園2017 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0362?year=2017

考察過程

1. 往復できるかという問題だが、「左端から右端へ移動できるか」の判定が作れれば、右端から左端への問題へすぐ変換できるので、片道できるかという問題について考える
2. d[i]/10をした時の整数部が移動できる添字の距離になる
3. 例えばトランポリンiに移動可能ということは、i+d[i]/10まで移動可能になったということ
4. 移動可能になる範囲は0から単調に伸びていく
5. 移動可能な右端を保持しながら、先頭から見ていって判定すれば良さそう

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0362/review/3136478/hamayanhamayan/C++14

片道の判定問題を考えよう。
往復はreverse関数でDを反転させてもう一度、同じ問題を解く。
　
i番目のトランポリンを使った場合に進める範囲は[i,i+d[i]/10]である。
現在移動可能な最右添字をokとする。
これを更新しながら、左からトランポリンを見ていけばいい。

int N, D[301010];
//---------------------------------------------------------------------------------------------------
int check() {
    int ok = 0;
    rep(i, 0, N) {
        if (ok < i) return 0;
        chmax(ok, i + D[i] / 10);
    }
    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i];

    if (!check()) {
        printf("no\n");
        return;
    }

    reverse(D, D + N);

    if (!check()) {
        printf("no\n");
        return;
    }

    printf("yes\n");
}