読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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

問題はこちら
No.346 チワワ数え上げ問題 - yukicoder

前の問題と微妙にチワワ列の定義が違う
今回求めるものは「'c'ごとにそれより後ろにある'w'を2つ選ぶ場合の数を求め、その合計」となる。
ただしSのサイズが大きいので「前から見ていって、'c'を見つけるごとにそれより後ろの'w'の個数を数える」という方法ではTLEする。
なので発想を転換して後ろから数える!
(思いつかなかったので解説を読んだ)

後ろから'w'を見つける毎にカウントを増やしていって、'c'を見つけたらそれを利用して計算する

int main(){
	char s[100010];
	long m,t,n;
	gets(s);
	for(n=strlen(s);n--;){
		if(s[n]=='w')t++;
		//'w'が見つけたらカウンタtを増やす
		if(s[n]=='c')m+=t*(t-1)/2;
		//'c'を見つけたら、'w'はそれより後ろにt個あるのでそこから2個選ぶ方法はt*(t-1)/2
	}
	printf("%ld",m);
	return 0;
}

sの大きさをちょっとごまかして縮める

char s[99999];
long m,t,n=1e5;
main(){
	for(gets(s);n--;)s[n]-99?t+=s[n]=='w':(m+=t*~-t/2);
	m=!printf("%ld",m);
}

107B

16/06/17追記
後ろからの処理は再帰ってそれ100万回言われてるから

long t,m;
f(i){
	read(0,&i,1)&&f(0);
	t+=i=='w';
	m+=i-99?0:t*~-t/2;
	//i-99?t+=i=='w':(m+=t*~-t/2);と同じ長さなのでバラしてみた(無意味)

}
main(){t=!printf("%ld",m,f(0));}

94B

17/02/20追記
DPするだけじゃん
dp[0]…"c"の数
dp[1]…"cw"の数
dp[2]…"cww"の数
として、今見ている文字が
'c'ならdp[0]++
'w'ならdp[2]+=dp[1]、dp[1]+=dp[0]
それ以外なら何もしない
として更新していく

long c,s,w;
main(t){
	for(;read(0,&t,1);t-99?t==119?s+=w,w+=c:0:c++);
	s=!printf("%ld",s);
}

86B