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; }