Lyft Level 5 Challenge 2018 - Elimination Round : C. Permutation Game

これはEを飛ばしてFを解くべきだった…。
http://codeforces.com/contest/1033/problem/C

問題

　
1～Nのpermutationである数列Aを用いて、２人交互に数字を取りあうゲームを行う。
前の手番の人がA[i]を取ったとき、次の手番の人は以下を満たす要素jを1つ選ぶことができる。

• A[j]＞A[i]
• |i-j|はA[i]の倍数

先手が各要素を取った場合、先手後手どちらが必勝か答えよ。

解法

A[i]の大きい順に、勝者を確定させていけばよい。
各要素の次に選択できる要素の総数はO(N*調和級数(N))なので計算量は問題ない。

int N;
int A[101010];
int loose[101010];
pair<int,int> P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i]={A[i],i};
	}
	
	sort(P,P+N);
	reverse(P,P+N);
	
	FOR(j,N) {
		x=P[j].second;
		loose[x]=1;
		for(i=1;x+i*A[x]<N;i++) {
			y=x+i*A[x];
			if(A[y]>A[x] && loose[y]) loose[x]=0;
		}
		for(i=1;x-i*A[x]>=0;i++) {
			y=x-i*A[x];
			if(A[y]>A[x] && loose[y]) loose[x]=0;
		}
	}
	
	FOR(i,N) _P("%c",'A'+loose[i]);
	_P("\n");
	
	
	
}

まとめ

本番、Aがpermutationというのを見落として無駄に平方分割してしまった。