きままにものづくり

日々の気付いたことなんかを書いてます。

SRM650Div1Easy

問題

サイズNの文字列を考える。この文字列はAとBのみで構築されている。M個のポジションとその文字が与えられ、隣り合う文字が同じとなる箇所の個数が最小となるパターンの総数を求めよ。

解法

与えれた文字とその間の文字数で答えが求まる。
以下のような例を考える。
A**B
この場合は、
ABAB
と一意に決まる。
一方、
A**Aの場合は、
ABAA
ABAA
ABBA
の3つになる。
A****Aの場合は、
AB**BA
ABABAA
AABABA
となる。
このように、再帰でパターン数が求められる。
より注目していくと、常に*の数+1となる。

すべての間隔に対して上のパターンを求め、かけることで答えが求まる。

計算量

 O(M log M)

コード