競技プログラミング用 知識集積所
ABC441E - A ＞ B substring
最終更新：
Bot(ページ名リンク)
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
愚直にやると、O(N^3)かかり、圧倒的TLE。
そこで、ひとまず累積和でO(N^2)にすることを考える。
文字列の開始からi文字目までにAが何個、Bが何個あるかをカウントしておく。
すると区間[L,R)にあるAの個数、Bの個数はそれぞれ引き算一発で出せるようになる。
つまり、区間[L,R)が条件を満たすかどうかの判定がO(N)からO(1)に高速化される。
これで全体がO(N^2)になる。
文字列の開始からi文字目までにAが何個、Bが何個あるかをカウントしておく。
すると区間[L,R)にあるAの個数、Bの個数はそれぞれ引き算一発で出せるようになる。
つまり、区間[L,R)が条件を満たすかどうかの判定がO(N)からO(1)に高速化される。
これで全体がO(N^2)になる。
しかし、これでもまだTLEなので、さらなる高速化を考える。
区間[L,R)にあるAの個数は、numA(R)-numA(L)である。（numA(x)は、x以前にあるAの個数の意味）
同様に、Bの個数は、numB(R)-numB(L)である。
で、判定は、numA(R)-numA(L)>numB(R)-numB(L)で行うことになる。
これを少し変形すると、numA(R)-numB(R)>numA(L)-numB(L)となる。
つまり、numA(x)-numB(x)を全て計算して、「その値より小さい計算結果は今までに何回出たか？」を確認すればそのRの値に対応するLの個数がわかる。
区間[L,R)にあるAの個数は、numA(R)-numA(L)である。（numA(x)は、x以前にあるAの個数の意味）
同様に、Bの個数は、numB(R)-numB(L)である。
で、判定は、numA(R)-numA(L)>numB(R)-numB(L)で行うことになる。
これを少し変形すると、numA(R)-numB(R)>numA(L)-numB(L)となる。
つまり、numA(x)-numB(x)を全て計算して、「その値より小さい計算結果は今までに何回出たか？」を確認すればそのRの値に対応するLの個数がわかる。
これはFenwick木※を使えば高速に処理することが可能。
ただし、Fenwick木※を用いる方法は0以上の数にしか対応していないので、numA(R)-numB(R)+n>numA(L)-numB(L)+nという形に変形し、numA(x)-numB(x)+nの計算結果について考えればよい。
ただし、Fenwick木※を用いる方法は0以上の数にしか対応していないので、numA(R)-numB(R)+n>numA(L)-numB(L)+nという形に変形し、numA(x)-numB(x)+nの計算結果について考えればよい。
これでO(N*logN)で処理ができ、制限時間に間に合う。
解答例
注意点
long long型を使う。
文字列が全部Aだった場合、あらゆる部分文字列が条件を満たすので、int型をはみ出る場合がある。
