Codeforces ECR #164 : D. Colored Balls

なんかDでミス繰り返してるな…。
https://codeforces.com/contest/1954/problem/D

問題

N種類のボールがあり、それぞれの個数が与えられる。

これらを組にすることを考える。
各組は1個または2個のボールからなり、同じ色のボールを組み合わせることはできない。

ボールの種類の選び方は2^N通りある。
それぞれ、ボールの組合わせを最小化したときの組数の総和を求めよ。

解法

まず色の制限を除くと、ボールの総数cに対しceil(c/2)個の組ができる。
これらはDPでボールの総数とその組み合わせを数え上げ、計算しておく。

これ以上の組ができてしまうのは、1色のボールが過半数の個数を占めてしまう場合である。
個数の少ない順にボールの総数とその組み合わせを数え上げ、最大個数の種類のボールを選んだ時過半数となるケースにおいて、ceil(c/2)組より多くの組ができてしまうケースを数え上げよう。

int N,A[5050];
const ll mo=998244353;

ll dp[5050];
ll p2[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,5010) p2[i+1]=p2[i]*2%mo;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	//全部を数える
	dp[0]=1;
	ll ret=0;
	FOR(i,N) {
		(ret+=p2[N-1]*(A[i]/2))%=mo;
		for(j=N;j>=0;j--) (dp[j+A[i]%2]+=dp[j])%=mo;
	}
	FOR(i,N+1) (ret+=dp[i]*((i+1)/2))%=mo;
	
	//過半数になるもの
	ZERO(dp);
	dp[0]=1;
	FOR(i,N) {
		FOR(j,A[i]) {
			(ret+=mo-dp[j]*((A[i]+j+1)/2))%=mo;
			(ret+=dp[j]*A[i])%=mo;
		}
		for(j=5000;j>=0;j--) if(j+A[i]<=5000) (dp[j+A[i]]+=dp[j])%=mo;
		
	}
	
	
	
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

そんなに難しく見えないが、本番なんでミスしたんだろ。