九州大学プログラミングコンテスト2018 : F - Team Making

Eの方が簡単に感じたが。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_f

問題

N人でチームを組む。
各人には現在のレートが設定されている。
各チームは３人以下で、複数人でチームを組む場合は平均レートがK以下でなければならない。

チームの組は何通りか。

解法

bitDPで、チーム未結成の人のうち最も番号の若い人と、あと１・２名追加するケースを総当たりするだけ。

int N,K;
int A[20];
ll dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		A[i]-=K;
	}
	dp[0]=1;
	for(int mask=0;mask<1<<N;mask++) {
		x=0;
		while(mask&(1<<x)) x++;
		dp[mask | (1<<x)]+=dp[mask];
		for(y=x+1;y<N;y++) if((mask & (1<<y))==0) {
			if(A[x]+A[y]<=0) dp[mask | (1<<x) | (1<<y)]+=dp[mask];
			for(z=y+1;z<N;z++) if((mask & (1<<z))==0) {
				if(A[x]+A[y]+A[z]<=0) dp[mask | (1<<x) | (1<<y) | (1<<z)]+=dp[mask];
			}
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

平均周りの処理も特に工夫は要らないし、なんだったんだ。