Official

C - Dango Editorial by MMNMM


以下では、便宜上 - もレベル \(0\) のダンゴ文字列とします。 文字列中にレベルが \(0\) より大きいダンゴ文字列が存在しない場合、元の問題の答えは \(-1\) です。

右端に - があるダンゴ文字列(右ダンゴ文字列)と左端に - があるダンゴ文字列(左ダンゴ文字列)をそれぞれ分けて考え、それらのうち一番レベルが大きいもの(\({}=\) もっとも長いもの)のレベルを求めることとします。 しばらく、右ダンゴ文字列についてのみ考えます。

右ダンゴ文字列のうち最も長いものである可能性があるのは、ある - とその直前の o の \(0\) 個以上の連なりすべてのみを含む部分文字列です。 これらを極大な右ダンゴ文字列と呼ぶことにします。

例 : oo--o-oooo-o の極大な右ダンゴ文字列は oo- - o- oooo- の \(4\) つです。一般に、極大な右ダンゴ文字列の個数はその文字列に含まれる - の個数と等しいです。

すべての極大な右ダンゴ文字列のレベルを求めるのは、文字列を先頭から \(1\) 度走査すればよいので、\(O(N)\) 時間で可能です。

極大な右ダンゴ文字列についての処理が書けたら、文字列を反転したものについて同じ処理を行うことで極大な左ダンゴ文字列に対する処理を済ませることができます。
よって、\(O(N)\) 時間ですべての極大なダンゴ文字列のレベルが得られるので、これらの最大値を答えればよいです。

実装例は以下のようになります。

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    string S;
    cin >> S;

    unsigned ans{};

    for (unsigned flip{}; flip < 2; ++flip) {
        // 極大な右ダンゴ文字列のレベルを列挙する
        unsigned level{};
        for (unsigned i{}; i < N; ++i)
            if (S[i] == '-') {
                // '-' に対応する極大な右ダンゴ列のレベルは、直前までの 'o' の個数
                ans = max(ans, level);
                level = 0;
            } else
                ++level;
        // 文字列を反転
        reverse(begin(S), end(S));
    }

    if (ans)
        cout << ans << endl;
    else
        cout << "-1" << endl;

    return 0;
}

posted:
last update: