2525文字列分解 [第4回 ドワンゴからの挑戦状 予選 B]

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_b

解法

https://dwacon2018-prelims.contest.atcoder.jp/submissions/1970821

未証明解法。
問題の点数を見るとそんなに難しく考えずに解ける感じなので、簡単な貪欲を考えてみよう。
先頭から貪欲に2525文字列を作っていく。
　
変数ni := 2525…2のように2で終わっている不完全2525文字列の個数
変数nico := 2525...25のような2525文字列の個数
を更新しながら貪欲する。
　
文字'2'については、既に2525文字列があれば後ろにくっつけて、不完全2525文字列とする。
もし2525文字列が無いならば、新しく作る。
　
文字'5'については、不完全2525文字列の後ろにくっつけて2525文字列にする。
もし、不完全2525文字列が無ければ、分解が達成不可能なので-1を返す。
　
最後に不完全2525文字列が残っていれば、それも分解が達成不可能であるとする。

string S;
//---------------------------------------------------------------------------------------------------
int solve() {
    int ans = 0;
    int ni = 0, nico = 0;
    fore(c, S) {
        if (c == '2') {
            if (0 < nico) {
                ni++;
                nico--;
            }
            else {
                ans++;
                ni++;
            }
        }
        else {
            if (ni == 0) return -1;
            else {
                ni--;
                nico++;
            }
        }
    }
    if (0 < ni) return -1;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    cout << solve() << endl;
}