Tenka1 2019 C - Stones (緑色, 300 点)

これをもっと早く

問題へのリンク

問題概要

長さ の白黒列が与えられる。

最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。

制約

• 

考えたこと

つまりは「白白白白黒黒黒黒黒」のように

• 左 left 個が白
• 右 N - left 個が黒

という状態にしかなりえない。よって、この left を全探索すればよい。left = 0 (黒のみ) や、left = N (白のみ) もありうることに注意する。

left を決め打ちした時の答えは

• 区間 [0, left) についての黒の個数 (それを白にしなければならない)
• 区間 [left, N) についての白の個数 (それを黒にしなければならない)

の合計値で決まる。さて、上記のような区間 [0, left) や [left, N) についての黒や白の個数を高速に求める必要があるが、それは例えば「白の個数」「黒の個数」に関する累積和などを作ると で求められる。

よって各 left について で求めることができるので、全体として の計算量でできる。

#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
string S;

long long solve() {
    N = S.size();
    vector<int> whsum(N+1, 0);
    vector<int> blsum(N+1, 0);
    for (int i = 0; i < N; ++i) {
        whsum[i+1] = whsum[i] + (S[i] == '.' ? 1 : 0);
        blsum[i+1] = blsum[i] + (S[i] == '#' ? 1 : 0);
    }
    
    long long res = 1LL<<60;
    for (int left = 0; left <= N; ++left) {
        long long tmp = 0;
        // left を全部白に
        tmp += blsum[left] - blsum[0];
        
        // right を全部黒に
        tmp += whsum[N] - whsum[left];
        
        chmin(res, tmp);
    }
    return res;
}


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