問題はこちら
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
