Codeforces 387(#227 Div2 only) C. George and Number

問題

自然数の数列a[i]に対して次の操作を、要素が一つになるまで繰り返す。

• 好きなi, j（i != jかつa[i]≧a[j]）を選び、a[i]のうしろにa[j]を文字列としてくっつけて、新しくできた項をaに追加し、a[i], a[j]を削除する。

n桁の数字が与えられる。
このn桁の数字を作れるようなa[i]として、最も項数が多いものの項数はいくつか。
a[i]の全ての要素は1以上でなくてはならず、leading zeroがあってはならないことに注意。

制約条件

n≦10万

方針

0があったらそれは前の数字にくっつけるしかない。0を全部くっつけたあとは、
800 | 10 | 1 | 2 | 4 のようになる。以後仕切りで分割されてない数字の塊を単に塊と呼ぶ。

条件から、数は大きいものの後に小さいものしかくっつけられないので、結局先頭から塊をつなげていくしかないと考えてよい。
（真ん中あたりで一度塊を作って、先頭の塊の末尾に付け足すようなやり方は、先頭からつなげていっても、先に先頭が大きくなるため絶対に実現できる）

次の塊をくっつけられるときは、項数 += 1してよい。
次の塊をくっつけられない場合は、たとえば、
900 | 800 | 900900 | 1 みたいなときは、3番目の塊が無理。
このときは最初の3つの塊が最初からかたまっていたとするしかない。

つまり、つなげられない塊が出てきたら項数は1に戻る。

で、つなげられるかどうかは桁数が違ったら桁数だけで判断できて、
桁数が同じだったら愚直に見ればいい。
毎回桁数が同じだとしても、桁数は1, 2, 4, ...と増えていくのでlogn回しか比較が起きないため。

ソースコード

string s;

int main(){
	cin >> s;
	
	int pos = s.size();
	vector<pi> v;
	
	for(int i = s.size() - 1; i >= 0; i--){
		
		if(s[i] != '0'){
			
			v.pb(mp(i, pos));
			pos = i;
		}
	}
	
	reverse(all(v));
	
	int ans = 0;
	
	rep(i, v.size()){
		
		if(v[i].second - v[i].first < v[i].first){
			ans++;
			continue;
		}
		
		if(v[i].second - v[i].first > v[i].first){
			
			ans = 1;
			continue;
		}
			
		if(v[i].second - v[i].first == v[i].first){
			
			rep(j, v[i].first) if(s[j] < s[j + v[i].first]){
				ans = 0;
			}
		}
		ans++;
	}
	cout << ans << endl;
	
	return 0;
}