https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/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; }