AGC037 - E Reversing and Concatenating

AGC037-Eを解いた。

問題

整数 $N,K$ 、文字列 $S$ が与えられる。
$S$ ← ( $S$ + $reverse(S)$ )の長さ $N$ の連続部分列
という操作を $K$ 回行う。操作後の $S$ として考えられるもののうち、辞書順最小のものは?

解法

$m=S$ 内の最小文字
と置く。前からできるだけ $m$ を連続させることを考えると
$max(後ろから連続しているmの数 * 2,S中で連続しているmの数の最大値)*2^{K-1}$
個だけ連続させることができる。また、これが上界であることも $S中で連続しているmの数の最大値$ が一回の操作で高々二倍にしかならないことを踏まえれば明らか。
これを踏まえれば操作手順の候補が絞れ、全部試せばよい。( $K$ が十分に大きい場合には $m$ を $N$ 個連続させたものを出力すればよい)