ABC104-D:We Love ABC(400)

数え上げ 動的計画法

問題

https://beta.atcoder.jp/contests/abc104/tasks/abc104_d

長さ S の文字列 T が与えられる。T のうち 3 つ文字を選んだときに左から A, B, C となっている組み合わせの数を求めよ。

制約

  • 3 \leq |S| \leq 10^5

考え方

場合の数である。文字を 3 つ選ぶときに真ん中の B を固定して数え上げることにすると、求める場合の数は以下の 4 通りである。

  1. (A, B, C) と選ぶ場合
  2. (A, B, ?) と選ぶ場合
  3. (?, B, C) と選ぶ場合
  4. (?, B, ?) と選ぶ場合

事前にある位置 k における

  • a := k よりも左にある A の個数
  • l := k よりも左にある ? の個数
  • c := k よりも右にある C の個数
  • r := k よりも右にある ? の個数

を求めておく。

  1. (A, B, C) と選ぶ場合
    この場合は B を基準に右に何個 A があるか、左に何個 C があるか数えればいい。その場合に文字列の ? に関しては任意の文字 \{A, B, C\} にすることができるので ? が l+r 個ある場合は 3^{l+r} 通りの組み合わせになる。よってそれぞれ掛け合わせればよいので、
    a * c * 3^{l+r} 通り
    となる。パターン (2), (3), (4) の場合も同様の考え方で求めることができる。

  2. (A, B, ?) と選ぶ場合
    a * r * 3^{l+r-1} 通り

  3. (?, B, C) と選ぶ場合
    l * c * 3^{l+r-1} 通り

  4. (?, B, ?) と選ぶ場合
    l * r * 3^{l+r-2} 通り

文字が B or ? なる位置 k について
3^{l+r}ac + 3^{l+r-1}ar + 3^{l+r-1}lc + 3^{l+r-2}lr
\Leftrightarrow 3^{l+r-2} (3a + l) (3c + r)
を足し合わせれば良い。

別解(DP)

i 文字目までで作成することの文字列 ('a', 'ab', 'abc', パターン数)の個数を数え上げることで、文字列を前から順番に参照して個数を確定することができる。i 文字目でできる文字列の個数は i-1 文字目の文字列の個数によって一意に決まるためである。

詳細は以下のブログを参照されたい。
ABC104 参加記録 - ARMERIA

ポイント

  • 何に着目して数え上げるか
  • 3点選択は真ん中に着目
  • 範囲の個数は累積和

類題

雑記

本番は C に 1 時間くらいをかけてしまい、考察の時間をとることができなかった。Bに着目して数え上げるところまではわかったが、4 つのパターンの場合分けが不十分であった。