Quiz
https://yukicoder.me/problems/no/852
AC Code
https://yukicoder.me/submissions/363142
参考
yukicoder 218
— fine@競プロ (@refine_P) July 26, 2019
A Rubyでホイ。FAみたいです。やったね。
B 誤読とかオーバーフローしてつらい。各文字について一つも含まない区間を数え上げ。
D 素数の個数は少ないし、各素数ごとに指数を計算して比較。よく考えると累積和で前計算しとけばOK。
F FFTを使ったりするのか？ 全然わからん。
参考２ ngtkanaさん
https://yukicoder.me/submissions/362752
参考３ 解説の4
https://yukicoder.me/problems/no/852/editorial
解法
- 各文字ごとに分けて求めることができます(a, b, c.., zの26種類を別々に求める)
各連続部分文字列について全ての文字の種類を含んでいるものと仮定します
- |s|=6の場合を考えてみよう
- s = "aaaaaa" と仮定すると、部分文字列のとり方は、6+5+4+3+2+1
- 一般に N * (N+1) / 2
- 実際はaxxaxa (xはa以外)のようにスキマがあり、その部分は余分にカウントしている
- スキマごとに数える
- スキマの長さをMとすると、そこから取れる「aが存在しない部分文字列」はM * (M+1) / 2 個。これを引く
- 余分に数えてしまった分を引く。上記例の場合は、'a'について
- 6(6+1)/2 - 2(2+1)/2
もっと一般的に書くと
