Codeforces #862 : Div2 F2. Survival of the Weakest (hard version)

こっちはコードが短い。
https://codeforces.com/contest/1805/problem/F2

問題

N要素の数列Aに対するF(A)は、i＜jにおけるA[i]+A[j]を列挙したもののうち、小さい順に(N-1)個を並べたものである。
今N要素の整数列Aが与えられるので、F(F(F(...F(A)))))と、Fを(N-1)回適用したときにできる1要素の整数列の値を求めよ。

解法

A'を、Aの各要素からA[0]を引いたものとすると、
F(A')=F(A)+A[0]*2^(|A|-1)
となる。
とすると、毎ステップ先頭要素は0の場合を考えればよい。
詳細は割愛するが、各ステップでは数列の高々64要素までを考えればよく、以降の要素の影響は最終的に表れない。

あとは上記2点を踏まえFの定義に沿って愚直に計算すればよい。

int N;
int A[202020],B[64],C[64];
const ll mo=1000000007;
ll p2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,201010) p2[i+1]=p2[i]*2%mo;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	if(N==2) {
		cout<<(A[0]+A[1])%mo<<endl;
		return;
	}
	int K=min(N,64);
	ll ret=0;
	FOR(i,N) {
		(ret+=A[0]*p2[N-1-i])%=mo;
		x=A[0];
		priority_queue<pair<int,int>> Q;
		FOR(j,K) {
			A[j]-=x;
		}
		FOR(j,K-1) {
			C[j]=j+1;
			Q.push({-(A[j]+A[j+1]),j});
		}
		FOR(j,K) {
			auto p=Q.top();
			Q.pop();
			B[j]=-p.first;
			x=p.second;
			C[x]++;
			if(C[x]<K) Q.push({-(A[x]+A[C[x]]),x});
		}
		FOR(j,K) A[j]=B[j];
	}
	cout<<ret<<endl;
}

まとめ

これ本番時間中に64要素見ればいいってところに到達できる気がしないな…。