No.295

文字ごとに考えて最後に掛け算をする.

アルファベット a が $T$ の中に __aa___a_aaa のようにあるとする. このとき, $S_a$ の a を $(x_1, x_2, x_3)$ 個に振り分けたときの $T$ 数は,

$${}_{x_1}C_2 \cdot {}_{x_2}C_1 \cdot {}_{x_3}C_3$$

になる. すなわち, 連続する a が $T$ の中に $(y_1, y_2, y_3, \dots, y_k)$ という感じであるとき,

$$\sum_{i=1}^k x_i = S_a$$

という条件下で

$$\prod_{i=1}^k {}_{x_i}C_{y_i}$$

を最大化するという問題になる.

そこで最初に $y_i$ 個のアルファベットは割り当てておいて, 残りの $S_a - \sum y_i$ 個をどう割り当てるかを考える. これは各 ${}_nC_r$ のどの項に割り当てれば最も大きくできるかを考えればいい. ${}_nC_r$ に割り当てると値は

$$\frac{ {}_{n+1}C_r }{ {}_nC_r } = \frac{(n+1)!}{(n+1-r)!r!} \frac{(n-r)!r!}{n!} = \frac{n+1}{n+1-r}$$

倍になるので, 各項ごとにこの倍率を計算して優先順位付きキューに入れておいて, 順に更新していく.

ただし, $S_a - \sum y_i$ 回の更新が必要になるので, $S_a$ が大きい場合はこの方法は使えない.

そこで, $S_a \gt 10^7$ のときは, 値は最低でも $S_a^k$ 以上になるので, $k \geq 3$ の場合は $2^{62}$ を超えるのは確実なので hel である.

$k = 2$ のときは, $y_1 = y_2 = 1$ ならば等分に分けるのが最もよく, $y_1 \gt 1$ または $y_2 \gt 1$ ならば $2^{62}$ を超えるのは確実なので hel である.

$k = 1$ のときは, $y_1 = 1$ ならば $S_a$ が答えであり, $y_1 = 2$ ならば $S_a(S_a-1)/2$ が答えとなる. $y_1 \gt 2$ ならば $2^{62}$ を超えるので hel である.