Codeforces #706 Div1 : B. Let's Go Hiking

本番Pretest通してsystest落とした…。
https://codeforces.com/contest/1495/problem/B

問題

1～NのPermutationを用いて以下の2人対戦ゲームを行う。
先手・後手の順で、任意のindexを選ぶ、ただし両者重複するような選択はできない。
その後、両者交互にindexをインクリメントまたはデクリメントする。
ただし、先手は値が減少する方向、後手は値が増加する方向しか選択できない。
また、相手と同じindexになることは許されない。
インクリメントもデクリメントもできなくなると、その人は負けとなる。

先手必勝となる最初のindexは何通りか。

解法

まず、先手の初手は左右どちらにも移動できなければならない。
そうでないと、初手の移動先を後手にふさがれておしまいである。

左右どちらにも移動できる場合、後手が有利な方をふさいでくるはずなので、後手が最大限有利なケースでも先手が勝てるかを判定しよう。これは左右両方向でそれぞれ何手移動できるかで定まる。

int N,P[101010];
int L[2][101010],R[2][101010],D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i+1];
	FOR(i,N) {
		if(i&&P[i]<P[i+1]) L[0][i+1]=L[0][i]+1;
		if(i&&P[i]>P[i+1]) L[1][i+1]=L[1][i]+1;
	}
	for(i=N-1;i>=0;i--) {
		if(i!=N-1&&P[i+2]<P[i+1]) R[0][i+1]=R[0][i+2]+1;
		if(i!=N-1&&P[i+2]>P[i+1]) R[1][i+1]=R[1][i+2]+1;
	}
	multiset<int> S;
	FOR(i,N) S.insert(max(L[1][i+1],R[1][i+1]));
	
	
	int ret=0;
	for(i=1;i<N-1;i++) if(P[i]<P[i+1]&&P[i+1]>P[i+2]) {
		int a=L[0][i+1];
		int b=R[0][i+1];
		x=i+1-a;
		y=i+1+b;
		S.erase(S.find(max(L[1][x],R[1][x])));
		S.erase(S.find(max(L[1][y],R[1][y])));
		
		ret++;
		if(S.size()&&*S.rbegin()>=max(a,b)) ret--;
		else if(min(L[1][x],R[1][x])>=max(a,b)) ret--;
		else if(min(L[1][y],R[1][y])>=max(a,b)) ret--;
		else {
			if(a%2==1&&b%2==1) {
				ret--;
			}
			else if(a%2==1&&b%2==0&&(a>b||b-1>=a)) {
				ret--;
			}
			else if(a%2==0&&b%2==1&&(b>a||a-1>=b)) {
				ret--;
			}
			else if(a%2==0&&b%2==0) {
				if(a!=b) ret--;
			}
		}
		S.insert(max(L[1][x],R[1][x]));
		S.insert(max(L[1][y],R[1][y]));
	}
	
	cout<<ret<<endl;
	
}

まとめ

本番なんで落としたんだろ。