なんか大変だったようで。
https://atcoder.jp/contests/abc150/tasks/abc150_e
問題
N要素の整数列C[i]が与えられる。
01で構成されるN文字の文字列が2つS,Tがあったとする。
Sの1文字S[i]を選び0,1反転させるのにかかるコストは、C[i]*(S,Tで一致しない文字数)とする。
任意の順番で反転を繰り返し、SとTを最小コストで一致させることを考えよう。
S,Tが異なる全パターンにおいて、最小コストの総和を求めよ。
解法
S,Tが一致するパターンはどうせコスト0なので、S,Tは全パターン試すことを考えよう。
さらに、SとTの各文字は一致するかどうかだけが重要で0,1の具体的な値はどうでもよいので、T=000....の場合だけを考えよう。
最後にTのバリエーションの分(2^N)すればよい。
最小コストの実現法だが、不一致な要素数分コストに倍率がかかるので、コストが低い順に処理すればよい。
逆に各文字に対し、それよりコストの高い位置の不一致数分が重要である。
Cを降順に処理することを考える。
S[i]が不一致であることによるコストへの影響を考える。
iより手前に不一致な文字がk個あるのはComb(i,k)通りなので、i文字目以降に一致不一致が2^(N-(i+1))通りあることを考えるとComb(i,k)*(k+1)*(2^(N-(i+1))*C[i]だけコストに跳ね返る。
ここで、kに対しComb(i,k)*(k+1)の総和を取らなければならない。
この値をP(i)とする。Comb(n,k)+Comb(n,k-1)=Comb(n+1,k)であることを利用すると、P(i+1)=2*P(i)+sum(Comb(i,k))=2*P(i)+2^iとなる。
int N; ll C[202020]; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>C[i]; sort(C,C+N); reverse(C,C+N); ll p=1,q=1; FOR(i,N) q=q*2%mo; ll sum=1; ll ret=0; FOR(i,N) { q=q*(mo+1)/2%mo; (ret+=(C[i]*sum)%mo*q)%=mo; sum=(sum*2+p)%mo; p=p*2%mo; } cout<<ret*p%mo<<endl; }
まとめ
最終的な式はともかく、途中結構式がずれてFよりよっぽど苦戦した。