kmjp's blog

競技プログラミング参加記です

AtCoder ABC #150 : E - Change a Little Bit

なんか大変だったようで。
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よりよっぽど苦戦した。