問題

A B のみからなる文字列であって、以下をすべて満たすもの数を数えよ:

  • A をちょうど $N$ 文字含む
  • B をちょうど $M$ 文字含む
  • 先頭の文字は A
  • 末尾の文字は B
  • 部分文字列として AAA を含む

解説

初手で補集合をとる。 $M$ 個の B の隙間に合計で $N$ 個の A を挿入し、かつそれぞれの隙間に入る A は $0 \sim 2$ 個であるようなものを数えればよい。 B の隙間に ` ` A AA がそれぞれ何回出現するかの組は自由度 $1$ なので $O(N)$ 個しかなく、これらを固定すれば後は組合せ ${} _ n C _ r$ の式で $O(1)$ で求まる。 計算量は $O(N + M)$ ぐらい。

メモ

  • 「B の隙間に A を挿入」系の考え方は典型感あるけど、他の例がすぐに出てこなくて困る
  • (A?A?B+)* と書きたくなるが、含まれる個数に関する制約があるので (有限性で殴らない限りは) 正規表現では書けない

リンク