ARC104 B - DNA Sequence (400) - procon-kirokuyou

ARC104 B - DNA Sequence (400)

連続する空でない部分文字列なので区間のパターンは$ O(N^2)

愚直にやると1区間の判定に$ O(N)で全体で$ O(N^3)になりTLEする

累積和でその文字までの文字の表れた個数を持っておく

1区間の判定が$ O(1)で全体で$ O(N^2)になり間に合うようになる

問題: https://atcoder.jp/contests/arc104/tasks/arc104_b

提出: https://atcoder.jp/contests/arc104/submissions/17162775

#ARC104 #400pt #B #ARC #AtCoder