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

作りうるc.*w.*w列の数は？という問題。前から見てもTLEするケースが少なかったので、前から見てもなんとかなると思ってしまった。

yurahunaさんの解説の通り、後ろから出現したwの数を数えておき、cが出るたびに組み合わせを計算(wの数C2)します。あ、もちろんwの数が1以下の場合は組み合わせを計算してはいけません。本質的にはそういう問題です。

pakapa104.hatenablog.com

python3での解答コード。

def solve():
    s = input()[::-1]
    wc = 0
    
    res = 0
    for c in s:
        if c == "c":
            if wc >= 2:
                res += (wc * (wc-1)) // 2 # wの数C2
            continue
        if c == "w":
            wc += 1
    print(res)
    

if __name__=="__main__":
    solve()

ただ私がC++でゴリ推したら、なんとか前から見ても通りました。。。

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.precision(16);
	
	string s;
	cin >> s;
	
	vector<ll> cv;
	int wc = 0, cllen = 0;
	
	int slen = s.size();
	REP(i, slen) {
		char c = s[i];
		if(c == 'c') {
			cv.pb(0);
			cllen++;
			continue;
		}
		if(c == 'w') {
			REP(j, cllen) cv[j]++;
		}
	}
	
	ll res = 0;
	for(auto i : cv) {
		if(i < 2) break;
		res += (i * (i - 1)) / 2;
	}
	
	cout << res << endl;

}

31 / 300