はまやんはまやんはまやん

hamayanhamayan's blog

Attention [AtCoder Regular Contest 098 C]

https://beta.atcoder.jp/contests/arc098/tasks/arc098_a

解法

https://beta.atcoder.jp/contests/arc098/submissions/2571452

リーダーを全探索する。
i番目をリーダーとした場合に[1,i-1]番目がWを向いている人、[i+1,N]番目がEを向いている人が向く方向を変える人数となるので、この人数の最小値を答えとする。
[x,y]番目でWを向いている人が何人いるかは累積和を使うと高速に取得できる。

int N; string S;
int E[301010], W[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
 
    rep(i, 0, N) {
        if (S[i] == 'E') E[i] = 1;
        else W[i] = 1;
    }
 
    rep(i, 1, N) {
        W[i] += W[i - 1];
        E[i] += E[i - 1];
    }
 
    int ans = inf;
    rep(i, 0, N) {
        int sm = 0;
        if (i) sm += W[i - 1];
        sm += E[N - 1] - E[i];
        chmin(ans, sm);
    }
    cout << ans << endl;
}