Codeforces #227 Div2. C. George and Number

Div2 onlyなのでレートはつかないけど、CF227に参加。
Cで戸惑ってだいぶ時間をかけてしまい、ロスタイムにギリギリDを通した。
そのため、幸いABCDは本番中に正答できた。
http://codeforces.com/contest/387/problem/C

問題

数列Bに対して以下の処理を繰り返すことができるとする。

• B[i] >= B[j] かつ i < jとなるインデックスの対を選択し、B[i]とB[j]をBから削除し、B[i]とB[j]を文字列的に連結して、Bの末尾に加える。

ここで、上記処理を繰り返した結果、Bが単一要素の数列になったとする。
最後の単一要素の数値が与えられたとき、その数値を上記処理で生成できるようなBの初期状態のうち最大要素数を答えよ。
ただし、Bの各要素は正でなければならず、leading zeroはあってはならない。

解法

元の文字列の右側から要素を作っていく。

残された文字の一番右から、０以外の最初の数字が出てくるまでを要素の候補とする。
例えば、9555なら5、310200なら200となる。
候補を取り除いた残りの数字が、候補の数値より大きいなら、その要素をBの初期要素としてカウントし、残された文字について処理を続ける。
候補を取り除いた残りの数字が、候補の数値より小さいなら終了。

int L;
string P;

void solve() {
	int f,i,j,k,l,x,y,r=0;
	
	cin>>P;
	
	y=L=P.size();
	r=1;
	while(y>=0) {
		x=y-1;
		while(P[x]=='0') x--;
		if(x<0) break;
		i=x-(y-x);
		if(i<0) break;
		if(i==0 && P.substr(0,x)<P.substr(x,x)) break;
		r++;
		y=x;
	}
	_P("%d\n",r);
}

まとめ

本番は二分探索したりだいぶ手こずった。
これがDiv1Aで出てきたらまずいな…。