AtCoder Beginner Contest 268 F問題 Best Concatenation
問題
提出解答
問題の概要
からなる文字列
に対するスコア
を次のように定める.
に対して,
をみたす整数の組
の数を
とする.
個の
からなる文字列
に対して,
の並び替え
に対する
を全て考えた時のスコアの最大値を求めよ.
制約
は
からなる非空文字列
解法
を
の並び替えとし,
に対して,
を
の第
項と第
項を入れ替えて得られる並び替えとする. そして,
とする. このとき, について考える.
から
に変化する時, スコアの増減は次のようにして起こる.
にある
と
にある数字のペアが寄与する分だけスコアが減る.
にある
と
にある数字のペアが寄与する分だけスコアが増える.
このとき, よく見ると と数字のペアの要素はそれぞれ独立に選べることから,
にある
の数と数字の総和をそれぞれ
とする.
も同様に定義する.
である.
よって, 非負整数 に対して
を
と定義することによって,
このことから, スコアを最大にするためには, が昇順になるように
を並び替えればよい事がわかる.
は
のみから定まるから, 計算量
時間で適切な並び替えを求め, その文字列に対するスコアを求めれば良い.