Concatenation [CODE THANKS FESTIVAL 2018 D]

解説

https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664721

提出証明みたいな所があるが、貪欲で解く。
説明のため「頭の文字がその文字列においてアルファベット順で最小となる文字列」を「良い文字列」とする。
　
先頭から最長の良い文字列をどんどん取っていくのが、最適戦略。
その確からしさについては分からず出した。
　
貪欲の実装が少し複雑だが、先頭stについて、iを後ろに伸ばせるだけ伸ばして、最長の良い文字列を見つけていくというだけ。

string S;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
 
    N = S.length();
    int ans = 0;
    int st = 0;
    while (st < N) {
        ans++;
        int i = st + 1;
        while (i < N and S[st] < S[i]) i++;
        if (i == N) break;
        st = i;
    }
    cout << ans << endl;
}