perogram

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

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の数が高速に求められればいい
  • 累積和を使う

f:id:peroon:20190404055719j:plain

  • A : wの箇所だけ1を入れ、ほかは0の配列
  • Ac : 配列Aを後ろから累積した配列
    • (accumulateの意味でAcとしている)

計算量

  • 累積和を作るコストO(|S|)
  • 文字列を最初から走査してcが見つかる度にnCrして組み合わせを足していく O(|S|)
  • よってO(|S|)で解くことができました