AtCoder Grand Contest 060 A問題 No Majority
問題 atcoder.jp
提出解答
(今回は C++ での提出) atcoder.jp
問題の概要
英小文字からなる文字列 が以下の条件を満たすとき, この文字列はよい文字列であるという.
の長さ
以上の連続部分文字列で以下を満たすものが存在しない.
- 過半数を占める英小文字が存在しない.
英小文字及び からなる長さ
の文字列
が与えられる.
にある
の数を
としたとき,
にあるそれぞれの
を好きな英小文字に置き換えて英文字列を得る方法は
通りであるが, そのうち, 得られる文字列がよい文字列であるような
の置き換えの方法を求めよ.
制約
は英小文字及び
からなる長さ
の文字列
解法
いい文字列について, 以下が成立する.
英小文字列 において, 以下は同値である.
はいい文字列である.
にある任意の長さ
または
の連続部分列において, その連続部分列に同じ英小文字がない.
よって, の
を置き換える方法で, 同じ英小文字が連続または
つあきで登場しないような埋め方の数を求めることになる.
動的計画法で解く. で英小文字全体の集合とする.
に対して,
を
文字目まで決定していて,
文字目が
,
文字目が
であるような置き換えの数
とする.
ベースケースは のときで,
に対して, 最初の
文字が
となり得るならば,
, なり得ないならば,
(
のときは必ずなり得ないになることに注意) である.
更新式について, 最後の2文字が であるとき,
として可能なのは
であり, これで全部である.
よって, 次のように更新すればよい.
ならば,
となる
に対して,
ならば,
となる
に対して,
以上の動的計画法によって, 求めるべき解答は
である.
英小文字の数を とすると, この問題を
時間で解くことができる.