hitoare日記

たまに書きます

E - Change a Little Bit (AtCoder Beginner Contest 150)

公式解説と解法が違っていたので。

問題リンク

atcoder.jp


問題概要

長いので省略

解法

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

感想

難しい。