PCK17-2

一覧・参加感想記事

問題公式PDF
AOJ

1-5問目
6問目←ここ
7問目

6:トランポリン

まず10で割っておいて、左右にいくつ動けるか計算しておきます。それをd[i]とします

行きを考えます。
iを0からカウントアップさせていきます。
今iにいるとしたら、i+d[i]まで行けますね。
これをcangoとしましょう。
そのとき、今までのcangoより大きくなければ、
今までで最大の場所から飛べばいいので、更新しなくてもいいです。
こうやって次にいけなくなるか、n-1にたどり着いたら終了です。
n-1にたどり着いていたら、同様に帰りも計算します。
計算量はO(N)です。

#include <iostream>
#include <algorithm>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define RREP(i,n) RFOR(i,0,n)

const int _N = 3e5 + 100;

int n;

int d[_N];
int main(){
    cin >> n;
    REP(i, n){
        cin >> d[i];
        d[i] /= 10;
    }

    // 行き
    int i=0, cango=0;
    for(;i <= min(cango, n-1);i++){
        cango = max(cango, i+d[i]);
    }
    if(cango<n){
        cout << "no" << endl;
        return 0;
    }

    // 帰り
    i=0;cango=0;
    for(;i <= min(cango, n-1);i++){
        cango = max(cango, i+d[n-1-i]);
    }
    if(cango<n){
        cout << "no" << endl;
        return 0;
    }

    cout << "yes" << endl;
}

本番はBITで殴ったんですが、上記のとおり、簡単でしたね。
O(N log N)
良くないですよ、ちゃんと考察しないとな…
WAを生やしてしまったし、エンバグして時間使ってしまった…

#include <iostream>
#include <algorithm>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define RREP(i,n) RFOR(i,0,n)

const int _N = 3e5 + 100;

int n;

/// --BIT--

struct BIT {
    int data[_N+1];
    void init(int n){
        REP(i, n+1){
            data[i] = 0;
        }
    }
    void add(int i, int x){
        i++;
        while(i<=n){
            data[i]+=x;
            i+=i&-i;
        }
    }
    // return sum of [0, i]
    // max is 3e5 -> int
    int sum(int i){
        i++;
        int s = 0;
        while(i>=1){
            s += data[i];
            i-=i&-i;
        }
        return s;
    }
};

/// --BIT--

BIT tree;
int d[_N];
int main(){
    cin >> n;
    REP(i, n){
        cin >> d[i];
        d[i] /= 10;
    }
    tree.init(n);
    tree.add(0, 1);
    tree.add(1, -1);
    REP(i, n-1){
        if(tree.sum(i) > 0){
            tree.add(i+1, 1);
            int t = i+1+d[i];
            if(t<n)tree.add(t, -1);
        }
    }

    if(tree.sum(n-1) == 0){
        cout << "no" << endl;
        return 0;
    }

    tree.init(n);
    tree.add(0, 1);
    tree.add(1, -1);
    REP(i, n-1){
        if(tree.sum(i) > 0){
            tree.add(i+1, 1);
            int t = i+1+d[n-1-i];
            if(t<n)tree.add(t, -1);
        }
    }

    if(tree.sum(n-1) == 0){
        cout << "no" << endl;
        return 0;
    }
    cout << "yes" << endl;
}