公式解説と解法が違っていたので。
問題リンク
問題概要
長いので省略
解法
Cが小さいものからとる方が良いので、まずCを小さい順にソートする。
動的計画法によって答えを求める。
dp[i] = (i文字目まで見た時のfの総和)とする。
1文字の文字列組は(1,0),(0,1)があるので\(dp[0] = C_0 \times 2 \)である。
dp[i-1]が求まっているとする。
文字列の組(S,T)に対しそれぞれ1文字足した文字列の組は(S+'0',T+'0'),(S+'0',T+'1'),(S+'1',T+'0'),(S+'1',T+'1')がある。
元のS,TでのCの寄与は、1文字足した時に(S+'0',T+'0')と(S+'1',T+'1')ではそのまま、(S+'0',T+'1'),(S+'1',T+'0')では1ずつ増える。
j (< i) に対しj文字目が異なり、さらにi文字目も異なる(S,T)の組は\(2 \times 2 \times 4^{i-1} \)個ある。
i文字目が異なる(S,T)の組は\(2 \times 4^i\)個ある。
よって、\[dp[i] = dp[i-1] \times 4 + C_i \times 2 \times 4^i + {\sum_{j=0}^{i-1} C_j} \times 4^i \] となる。
2の累乗と累積和を前計算すると高速に計算できる。
dp[N-1]が答え。
提出
https://atcoder.jp/contests/abc150/submissions/9399401
感想
難しい。