yukicoder No.346 - チワワ数え上げ問題

問題

http://yukicoder.me/problems/no/346

解法

逆側からwの数を数えながら走査します. 今見ている文字が'c'のとき, その'c'に対しては今まで数えてきた'w'の中から二つを選ぶことにより'cww'を作ることができます. これを全ての'c'について行えば答えを求めることができます.

ソースコード

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

typedef long long ll;

string S;

void Solve() {
    ll ans = 0, w_cnt = 0;
    reverse(S.begin(), S.end());

    for (int i = 0; i < S.size(); i++) {
        if (S[i] == 'c') {
            ans += w_cnt * (w_cnt - 1) / 2;
        } else if (S[i] == 'w') {
            w_cnt++;
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> S;

    Solve();

    return 0;
}

感想

ちわわがいっぱい.