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; } } }