アルゴリズム忘備録

競技プログラミングとかデータ分析とか

B: Reverse and Compare - AtCoder Grand Contest 019

agc019.contest.atcoder.jp

 

文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか?

 

左の文字から順に数えていく。今見ている文字がcのとき、そこより右の文字がすべてc以外なら右にある文字数だけ、反転したら別の文字列が構成できる。もし、cがk>0 個あるとき、その反転は両脇のcを除いた反転と同じなので、現時点ではカウントしないこととする。こうやって和をとっていけば全部の組み合わせがカウントできる。

 

アルファベットはa-zなので、これらの文字のカウントの累積和を作っておくことで、あるインデックスより左にある特定の文字、と言うものをO(1)でカウントできる。合わせて計算量はO(N)。