名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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

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

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


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

pakapa104.hatenablog.com


python3での解答コード。

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

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