Quiz
https://yukicoder.me/problems/no/346
Submit
https://yukicoder.me/submissions/335255
解法
- 各cを見つけたとき、後ろにいくつwがあるかが気になる
- 例えば後ろにwが5個あるとすれば、5C2の組み合わせがある
- 5個から2個を選ぶ組み合わせ
- cを見つけたときのindexがiだったとして、それ以降(i+1)以降のwの数が高速に求められればいい
- 累積和を使う
- A : wの箇所だけ1を入れ、ほかは0の配列
- Ac : 配列Aを後ろから累積した配列
- (accumulateの意味でAcとしている)
計算量
- 累積和を作るコストO(|S|)
- 文字列を最初から走査してcが見つかる度にnCrして組み合わせを足していく O(|S|)
- よってO(|S|)で解くことができました
