Codeforces Round #385 (Div. 1)

Codeforces初めまして。

A	B	C	D	E	Place
00:08	00:18	00:48	-	-	14th

A:
算数と変な実装。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[1100];
int UF[1100];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;
	UF[a]+=UF[b];UF[b]=a;
}
int has[1100];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%d",p+i);
		p[i]--;
	}
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);s--;t--;
		UNION(s,t);
	}
	for(int i=0;i<c;i++)has[FIND(p[i])]=1;
	int ms=0;
	int ret=-b;
	for(int i=0;i<a;i++){
		if(UF[i]<0){
			int sz=-UF[i];
			ret+=sz*(sz-1)/2;
			if(has[i]){
				ms=max(ms,sz);
			}
		}
	}
	//printf("%d\n",ret);
	for(int i=0;i<a;i++){
		if(UF[i]<0&&has[i]==0){
			ret+=ms*(-UF[i]);
			ms+=-UF[i];
		}
	}
	printf("%d\n",ret);
}

B:
i-th bitが1のもの全部/0のもの全部のを計算しておけば全部に答えられる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int ret[1100];

int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		ret[i]=mod;
	}
	for(int i=0;i<10;i++){
		vector<int>v;
		for(int j=0;j<a;j++)if(j&(1<<i)){
			v.push_back(j);
		}
		if(v.size()){
			printf("%d\n",(int)v.size());
			for(int j=0;j<v.size();j++){
				if(j)printf(" ");
				printf("%d",v[j]+1);
			}
			printf("\n");fflush(stdout);
			for(int j=0;j<a;j++){
				int f;scanf("%d",&f);
				if(!(j&(1<<i)))ret[j]=min(ret[j],f);
			}
		}
		v.clear();
		for(int j=0;j<a;j++)if(!(j&(1<<i))){
			v.push_back(j);
		}
		if(v.size()){
			printf("%d\n",(int)v.size());
			for(int j=0;j<v.size();j++){
				if(j)printf(" ");
				printf("%d",v[j]+1);
			}
			printf("\n");fflush(stdout);
			for(int j=0;j<a;j++){
				int f;scanf("%d",&f);
				if((j&(1<<i)))ret[j]=min(ret[j],f);
			}
		}
	}
	printf("-1\n");
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}
	printf("\n");fflush(stdout);
}

C:
dp[i][j]=集合i、赤でj得したときの青の得の最大値
普通に典型なのにみんな遅いし自分も遅い。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int dp[1<<16][130];
char in[20];
int p[20];
int q[20];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%s%d%d",in+i,p+i,q+i);
	}
	for(int i=0;i<(1<<a);i++)for(int j=0;j<130;j++)dp[i][j]=-mod;
	dp[0][0]=0;
	int rn=0;
	for(int i=0;i<a;i++)if(in[i]=='R')rn++;
	for(int i=0;i<(1<<a);i++){
		int R=0;
		int B=0;
		for(int j=0;j<a;j++){
			if(i&(1<<j)){
				if(in[j]=='R')R++;
				else B++;
			}
		}
//		printf("%d: %d %d\n",i,R,B);
		for(int j=0;j<130;j++){
			if(dp[i][j]<0)continue;
			//printf("%d %d: %d\n",i,j,dp[i][j]);
			for(int k=0;k<a;k++){
				if(i&(1<<k))continue;
				dp[i+(1<<k)][j+min(R,p[k])]=max(dp[i+(1<<k)][j+min(R,p[k])],dp[i][j]+min(B,q[k]));
			}
		}
	}
	int rsum=0;
	int bsum=0;
	for(int i=0;i<a;i++){
		rsum+=p[i];
		bsum+=q[i];
	}
	int ret=mod*2;
	for(int i=0;i<130;i++)ret=min(ret,max(rsum-i,bsum-dp[(1<<a)-1][i]));
	printf("%d\n",ret+a);
}

D:
O(N^2 log N log ans)の解は有名だが間に合わなさげ。
反転を使うらしい。また今度。