太鼓の名人 (Taiko Expert) [Summer Festival Contest 2018 B]

https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_b

考察過程

1. 全探索する対象を考えてみる
2. DとKの境目が全探索できそう
3. よくよく考えると、境目が決まると、DDDDKKKKが作れるか作れないかを判別することができる

解法

https://beta.atcoder.jp/contests/summerfes2018-div2/submissions/3070714

DとKの境目を全探索して数え上げる。
境目をcとすると、

• [0,c)の範囲にKがあってはいけない
• [c,N)の範囲にDがあってはいけない

ことがわかるので、この判定をして、大丈夫ならその境界のDK列は作れる。
判定はO(1)でもできるが、制約的にO(N)でも間に合う。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    int ans = 0;
    rep(c, 0, N + 1) {
        // [0,c) -> D
        // [c,N) -> K
        int ok = 1;
        rep(i, 0, c) if (S[i] == 'K') ok = 0;
        rep(i, c, N) if (S[i] == 'D') ok = 0;
        if (ok) ans++;
    }
    cout << ans << endl;
}