Codeforces #237 Div2 E. Maze 1D

本番1時間以上かかったけど最終的に解けてよかった。
http://codeforces.com/contest/404/problem/E

問題

'L'・'R'からなる文字列が与えられる。
初期状態で原点にいるロボットは、文字列を先頭から1文字ずつ呼ぶたびに1マス左または右に移動する。
ここで、最終的に到達するマスはそれまでの過程で複数回通らないようにしたい。

ロボットが最初に移動を始める前、幾つかブロックを置くことができる。
ロボットがブロックを置いたマスに移動しようとすると、その移動はキャンセルされ、移動できず次の文字の処理に移る。

条件を満たすブロックの置き方のうち、ブロック数を最少化し、その上でブロックを置く位置の組み合わせ数を答えよ。

解法

以下では、最後の移動が右の場合全体を左右反転させておく。
よって、最後の移動は左となる。

この状態で題意を満たすには、原点からしばらく右に移動し、最後は原点より左に移動して終わらなければならない。
この時置くブロックは多くて1個で良い。最後左に移動して終わるので、原点の左側にブロックを置く意味はなく右側だけである。

座標P(>0)にブロックを追いて条件を満たせる場合、P-1にブロックを置いても条件を満たせる。
このことから、条件を満たせる最大のPを求めればよい。
後はブロックの位置を二分探索で求めるだけ。

Pが無限に大きくても条件を満たせる場合は、ブロックがなくても条件を満たせるのでその場合ブロックを置かない（組み合わせ数１）と回答する。

int L;
string S;
int num[2000003];
int D[1000001];

int ok(int sp) {
	ZERO(num);
	int x=1000000;
	int i;
	
	num[x]=1;
	FOR(i,L) {
		x+=(S[i]=='L')?-1:1;
		if(x>=1000000+sp) x=1000000+sp-1;
		num[x]++;
	}
	if(num[x]==1) return 1;
	return 0;
	
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	L=S.size();
	
	// rev
	if(S[L-1]=='R') FOR(i,L) S[i]=(S[i]=='L')?'R':'L';
	
	if(ok(1<<30)) return _P("1\n");
	if(ok(1)==0) return _P("0\n");
	
	int LL=1,RR=L;
	FOR(i,30) {
		int mm=(LL+RR)/2;
		if(ok(mm)) LL=mm;
		else RR=mm-1;
	}
	
	while(ok(LL)) LL++;
	
	_P("%d\n",LL-1);
}

まとめ

本番はしばらくスタックとか考えていたけど、最終的に二分探索に気づけて良かった。