はむへい’s diary

ねむいです。

ABC104-D we Love ABC 解説

ABC104-D We Love ABC 解説

問題URL  

僕が使った解法を解説します。

まず、1つのBに注目します。そのBをとりあえずABCのBとして定めた時に、「Bの左側の文字列を全列挙した時に現れるAの個数」と「Bの右側の文字列を全列挙した時に現れるCの個数」をかけ算した値が、そのBをABCのBとして扱った時のABCの総数となります。

これを求めてみましょう。Bの左側のAの個数をX,Bの左側の?の個数をYとします。 まず、Bより左側の一つのAについて着目してみましょう、このAは、列挙されうる全てのBより左側の文字列に現れるので、3Y回現れることになります。これは全てのBより左側のAについて言えるので、Bより左側の文字AがAとして現れる数の合計はX*3Y個であることがわかります。

次に、Bより左側の一つの?について着目してみましょう。この?が文字Aだとして考えた時、この?はこの?以外の?が変化した時の状態数分Aとして現れるので、この?がAとして現れる回数は3Y-1となります。これは全てのBより左側の?について言えるので、全てのBより左側の?がAとして現れる個数はY*3Y-1であることがわかります。

これを足すと、「Bの左側の文字列を全列挙した時に現れるAの個数」となります。同じようにして「Bの右側の文字列を全列挙した時に現れるCの個数」も求めることが出来ます。
双方を掛け算することによって、注目したBがABCのBとして扱われる時のABCの総数を求めることが出来ました。

全てのBまたは?についてこのような計算を行い、その総和をとることによってこの問題の答えとなります。

予めAの個数、Cの個数、?の個数を累積和で求めておき、3のべき乗を列挙しておいた上で(いらないかも)、全てのBまたは?についてこのような計算を行うことで、O(|S|)でこの問題を解くことができます。
僕の解答

最後に、今日はABCです。気張っていきましょう!!