けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 098 C - Attention (ARC 098 C) (茶色, 300 点)

累積和の典型問題

問題概要

WWEWEEWWEE のような文字列が与えられる。

文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。

制約

  •  2 \le N \le 3 \times 10^{5}

解法

累積和を用いる。

#include <iostream>
#include <string>
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
string S;

int solve() {
    int allE = 0, allW = 0;
    for (int i = 0; i < (int)S.size(); ++i) {
        if (S[i] == 'E') ++allE;
        else ++allW;
    }
    int res = (int)S.size();
    int curE = 0, curW = 0;
    for (int i = 0; i < (int)S.size(); ++i) {
        int migiE = allE - curE;
        if (S[i] == 'E') --migiE;
        chmin(res, curW + migiE);
        
        if (S[i] == 'E') ++curE;
        else ++curW;
    }
    
    return res;
}

int main() {
    while (cin >> N >> S) {
        cout << solve() << endl;
    }
}