Codeforces #652 Div2 F. BareLee

これ本番に自信をもって通すとしんどいタイプだ。
http://codeforces.com/contest/1369/problem/F

問題

2人で交互に行うターン制のゲームを行う。

このゲームはT個のラウンドからなる。
各ラウンドは2整数S,Eで定義される。
自分の手番では、Sを倍にするかインクリメントするか選択できる。自分の点の結果、SがEを超えると負けとなる。
勝ち負けが確定すると、次のラウンドに移る。その際、直前のラウンドの敗者が次のラウンドの先手となる。

先手が、最終的に勝ち確定できるか、負け確定できるかをそれぞれ答えよ。

解法

個々のラウンドについて、win(s,e)とlose(s,e)を先手が勝ち確定・負け確定に持っていけるかを示すブール値とする。

• win(s,e)は
  • eが奇数なら、sが奇数かどうかがwin(s,e)になる
  • eが偶数なら
    • e/2 ＜ s ≦eなら、sが奇数かどうかがwin(s,e)になる
  • e/4 ＜ s ≦ e/2ならwin(s,e)=true
  • s＜e/4ならwin(s,e)=win(s,e/4)
• lose(s,e)は
  • e＜2*sならlose(s,e)=true
  • それ以外の場合lose(s,e)=win(s,e/2)

あとは、各ラウンドのあと、最初の先手が、次のラウンドで先手・後手いずれを取れるかを順次求めて行く。

int T;
ll S[101010],E[101010];

int win[101010],lose[101010];

int canwin(ll s, ll e) {
	if(s==e) return 0;
	if(s>=e) return 1;
	if(e%2) {
		return !(s%2);
	}
	else {
		if(s*2>e) return (e-s)%2;
		if(4*s>e) return 1;
		return canwin(s,e/4);
	}
}

int canlose(ll s,ll e) {
	if(e<2*s) return 1;
	return canwin(s,e/2);
}


void solve() {
	int i,j,k,r,x,y; string s;
	
	cin>>T;
	FOR(i,T) {
		cin>>S[i]>>E[i];
		
		win[i]=canwin(S[i],E[i]);
		lose[i]=canlose(S[i],E[i]);
	}
	int w=1,l=0;
	
	FOR(i,T) {
		if(w==l) break;
		
		if(w) {
			w=lose[i];
			l=win[i];
		}
		else {
			w=!lose[i];
			l=!win[i];
		}
		
	}
	
	cout<<l<<" "<<w<<endl;
	
}

まとめ

このwinとlooseの条件をさらっと分析できる気がしない。