AtCoder Grand Contest 060 A問題 No Majority

提出解答

(今回は C++ での提出) atcoder.jp

問題の概要

英小文字からなる文字列 $X$ が以下の条件を満たすとき, この文字列はよい文字列であるという.

の長さ以上の連続部分文字列で以下を満たすものが存在しない.
- 過半数を占める英小文字が存在しない.

英小文字及び ${\tt ?}$ からなる長さ $N$ の文字列 $S$ が与えられる. $S$ にある ${\tt ?}$ の数を $Q$ としたとき, $S$ にあるそれぞれの ${\tt ?}$ を好きな英小文字に置き換えて英文字列を得る方法は $26^Q$ 通りであるが, そのうち, 得られる文字列がよい文字列であるような ${\tt ?}$ の置き換えの方法を求めよ.

制約

$2 \leq N \leq 5000$
$S$ は英小文字及び ${\tt ?}$ からなる長さ $N$ の文字列

解法

いい文字列について, 以下が成立する.

英小文字列 $T$ において, 以下は同値である.

$T$ はいい文字列である.
$T$ にある任意の長さ $2$ または $3$ の連続部分列において, その連続部分列に同じ英小文字がない.

証明

長さ $2$ または $3$ の連続部分列において, その連続部分列に同じ英小文字が合った場合, $2$ 個中 $2$ 個または $3$ 個中 $2$ 個が同じ文字である連続部分列になり, これは過半数を占めているので, よい文字列ではない.

一方で, 長さ $4$ 以上の文字列で過半数を占める英小文字がある連続部分列が存在するとする. このとき, この文字列を半分で区切ることによって, どちらか一方が長さが元の半分であり, 過半数を占める英小文字がある連続部分列になる. よって, これを繰り返すことによって, 長さ $2$ または $3$ の連続部分列で, その連続部分列に同じ英小文字が存在するようなものが得られる.

よって, $S$ の ${\tt ?}$ を置き換える方法で, 同じ英小文字が連続または $1$ つあきで登場しないような埋め方の数を求めることになる.

動的計画法で解く. $\mathcal{A}$ で英小文字全体の集合とする. $2 \leq i \leq N, \alpha, \beta \in \mathcal{A}$ に対して, ${\rm DP}[i, \alpha, \beta ]$ を

$i$ 文字目まで決定していて, $(i-1)$ 文字目が $\alpha$ , $i$ 文字目が $\beta$ であるような置き換えの数

とする.

ベースケースは $i=2$ のときで, $\alpha, \beta \in \mathcal{A}$ に対して, 最初の $2$ 文字が $\alpha \beta$ となり得るならば, ${\rm DP}[2, \alpha, \beta ]=1$ , なり得ないならば, ${\rm DP}[2, \alpha, \beta]=0$ ( $\alpha=\beta$ のときは必ずなり得ないになることに注意) である.

更新式について, 最後の2文字が $\alpha, \beta$ であるとき, $\gamma \in \mathcal{A}$ として可能なのは $\gamma \neq \alpha, \beta$ であり, これで全部である.

よって, 次のように更新すればよい.

$S_i ={\tt ?}$ ならば, $\alpha \neq \beta, \alpha \neq \gamma, \beta \neq \gamma$ となる $\alpha, \beta, \gamma \in \mathcal{A}$ に対して, ${\rm DP}[\beta, \gamma] \xleftarrow{{\rm add}} {\rm DP}[\alpha, \beta ]$
$S_i \neq {\tt ?}$ ならば, $\alpha \neq \beta, \alpha \neq S_i, \beta \neq S_i$ となる $\alpha, \beta \in \mathcal{A}$ に対して, ${\rm DP}[\beta, S_i] \xleftarrow{{\rm add}} {\rm DP}[\alpha, \beta ]$