WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #174 Div2 D "Cow Program"

問題

http://codeforces.com/contest/284/problem/D

あるプログラムではx yという2つの変数があり、
正の整数の配列a(1), a(2), a(3).... a(N)に以下のような操作を行う。

1.  初期値はx=1, y=0であり、各ステップ後にx <= 0又はx > Nとなったら
  即座にプログラムを中止する。

2.  a(x)の値をxとyに足す。

3.  a(x)の値をyに足し、xからは引く。

4.  このプログラムは、中止になるまで操作2. 3.を交互に実行する。(最初は2. 次は3.)
  なので2. 3. 2. 3. ... と繰り返し実行していく。

配列はa(1)を除くa(2),a(3),a(4)...a(N)が与えられる。
i, a(2), a(3),...a(N) (1 <= i <= N-1)として、
それぞれのiでプログラムが終了した時のyの値を出力せよ。
プログラムが永久に終了しない場合は-1を出力せよ。

制約

2 <= N <= 2 * 10^5
1 <= 配列の値 <= 10^9

考えた事

素直にやったらO(N*N)になるな・・

既に訪れたインデックス(xの方向も一致)であれば、
永久ループになるので、訪れフラグを持っておく。

あと、配列のインデックス・次xが足されるか引かれるか、のそれぞれで、
yがこれからいくつ足されて終了するのか・・・をメモしておく。
永久ループの場合は-1とめもっておく。

TLE

訪れフラグを各iにおいて、memsetでクリアしてたから遅かった。
前のiの時点で訪れフラグがtrueになっていれば、必ずメモが残されているため、
リセットする必要はなかった。

AC

ソースコード

typedef long long ll;

const int MAX_N = 200010;
int N;
int arr[MAX_N];

// このインデックスでyはあといくつ増加してプログラムが終了するか
// 0は未チェック -1は永久ループ
// memo[1~N] 次x増加時 
// memo[N+1~N*2] 次x減少時
ll memo[MAX_N*2];

// このインデックスを訪れたかフラグ
// vis[1~N] 次x増加時 
// vis[N+1~N*2] 次x減少時
bool vis[MAX_N*2]; 

int main() {

    // 入力
    cin >> N;
    for( int i = 2; i <= N; i++ ){
        cin >> arr[i];
    }

    // memoを初期化
    for( int i = 0; i < MAX_N; i++ ){
        memo[i] = 0;
    }

    // iで回す
    for( int a1 = 1; a1 <= N - 1; a1++ ){
        arr[1] = a1;
        bool isInc = true;
        ll y = 0;
        int id = 1;
        vis[1] = false;
        memo[1] = 0;
        // yがいくつになるかを計算
        while( 1 <= id && id <= N ){
            int chk_i = isInc ? id : id + N;

            // メモしてたらそれを足して終わり
            if( memo[chk_i] == -1 ){
                y = -1;
                break;
            }
            if( memo[chk_i] != 0 ){
                y += memo[chk_i];
                break;
            }

            // この場所を現在のa1で使ったことがあったら永久ループ突入
            if( vis[chk_i] ){
                y = -1;
                break;
            }
            vis[chk_i] = true;

            y += arr[i];
            id += isInc ? arr[i] : -arr[i];
            isInc = !isInc;
        }

        // 出力
        printf( "%I64d\n", y );

        // メモしていないところまでメモる
        isInc = true;
        id = 1;
        while( 1 <= id && id <= N ){
            int chk_i = isInc ? id : id + N;
            if( memo[chk_i] != 0 ){
                break;
            }
            memo[chk_i] = y;
            if( y != -1 ) y -= arr[i];
            id += isInc ? arr[i] : -arr[i];
            isInc = !isInc;
        }
    }
}