tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

DDPC2016 Final

A:
おはよう

#include<stdio.h>
#include<algorithm>
using namespace std;
int t[]={100000,50000,30000,20000,10000};
int ans[200];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<min(a,5);i++){
		int b;scanf("%d",&b);b--;
		ans[b]+=t[i];
	}
	for(int i=0;i<a;i++)printf("%d\n",ans[i]);
}

B:
誤読した

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int f[110000];
int p[110000];
int q[110000];
vector<int>v[110000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
		
	}
	for(int i=0;i<a;i++){
		scanf("%d",q+i);
		v[p[i]].push_back(q[i]);
	}
	long long now=0;
	int left=0;
	int right=110000;
	while(left+1<right){
		int M=(left+right)/2;
		long long cur=0;
		priority_queue<int>Q;
		for(int i=101000;i>M;i--){
			for(int j=0;j<v[i].size();j++)Q.push(v[i][j]);
		}
		for(int i=M;i>0;i--){
			for(int j=0;j<v[i].size();j++){
				Q.push(v[i][j]);
			}
			if(Q.size()){
				cur+=Q.top();
				Q.pop();
			}
		}
		if(cur>=b)right=M;
		else left=M;
	}
	if(left>101000)printf("-1\n");
	else printf("%d\n",right);
 
}

C:
実 家 の よ う な 安 心 感

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
long long mod=1000000007;
char str[3100];
int n;
int K;
long long dp[3010][6020];
long long dp2[1600][6020];
int S=3010;
long long calc(int a,int b){
	int now=0;
	int pre=a+1;
	vector<int>v;
	vector<int>len;
	for(int i=a+1;i<b;i++){
		if(str[i]=='(')now++;
		else now--;
		if(now==0){
			calc(pre,i);
			v.push_back(pre);
			len.push_back(i+1-pre);
			pre=i+1;
		}
	}
	for(int i=0;i<=v.size();i++)for(int j=0;j<6020;j++)dp2[i][j]=0;
	dp2[0][S]=2;
	dp2[0][S-2]=1;
	dp2[0][S+2]=1;
	for(int i=0;i<v.size();i++){
		for(int j=0;j<6020;j++){
			if(dp2[i][j]==0)continue;
			for(int k=-len[i];k<=len[i];k++){
				if(j+k<0||j+k>=6020)continue;
				dp2[i+1][j+k]=(dp2[i+1][j+k]+dp2[i][j]*dp[v[i]][S+k])%mod;
			}
		}
	}
	long long ret=0;
	for(int i=-K;i<=K;i++){
		dp[a][S+i]=dp2[v.size()][S+i];
		ret=(ret+dp[a][S+i])%mod;
	}
	return ret;
}
int main(){
	scanf("%s%d",str,&K);
	n=strlen(str);
	long long ret=1;
	int cur=0;
	int pre=0;
	for(int i=0;i<n;i++){
		if(str[i]=='(')cur++;
		else cur--;
		if(cur==0){
			ret=ret*calc(pre,i)%mod;
			pre=i+1;
		}
	}
	printf("%lld\n",ret);
}

D:
苦手
うまく辺はってフロー

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
char in[2];
vector<int>go[210];
vector<int>ge[210];
int G[210][210];
int g[210][210];
int rev[210][210];
int UF[210];
int use[210];
const int D_MAX_V=2002;
const int D_v_size=2002;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];
 
void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1));
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
 
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 mh[210];
int deg[210];
int f[210];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<a;i++)G[i][i]=1;
	bool zt=false;
	for(int i=0;i<b;i++){
		int p,q;
		scanf("%d%d%s",&p,&q,in);
		p--;q--;
		if(in[0]=='O'){
			go[p].push_back(q);
			g[p][q]=1;
			G[p][q]=1;
			zt=true;
		}else{
			ge[p].push_back(q);
			G[p][q]=1;
		}
	}
	for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		G[i][j]|=G[i][k]&G[k][j];
	}
	if(!zt){
		printf("%d\n",a);
		return 0;
	}
	for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		if(g[i][j]&&G[j][i])rev[j][i]=1;
	}
	for(int i=0;i<a;i++)for(int j=0;j<a;j++)if(g[i][j]){
		UNION(i,j);
		use[i]=use[j]=1;
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(use[i]&&use[j]&&FIND(i)!=FIND(j)){
				printf("0\n");return 0;
			}
		}
	}
	for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		if(g[i][j]){
			deg[i]++;
			deg[j]--;
		}
		if(g[i][j]){
			f[i]++;f[j]++;
		}
	}
	int kt=0;
	vector<int>ks;
	for(int i=0;i<a;i++){
		kt+=f[i]%2;
		if(f[i]%2)ks.push_back(i);
	}
	if(kt>2){
		printf("0\n");return 0;
	}
	int qs=0;
	for(int i=0;i<a;i++){
		bool ok=false;
		for(int j=0;j<a;j++)if(g[i][j]||g[j][i])ok=true;
		if(ok)qs++;
	}
	if(kt==0){
		int S=a;
		int T=a+1;
		int req=0;
		for(int i=0;i<a;i++){
			if(deg[i]>0){
				req+=deg[i]/2;
				add_edge(S,i,deg[i]/2);
			}else if(deg[i]<0){
				add_edge(i,T,-deg[i]/2);
			}
		}
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)if(rev[i][j]){
			add_edge(j,i,1);
		}
		if(req==max_flow(S,T))printf("%d\n",qs);
		else printf("0\n");
	}else{
		int ret=0;
		int S=a;
		int T=a+1;
		int req=0;
		for(int i=0;i<a;i++)mh[i]=0;
		mh[ks[0]]=1;
		mh[ks[1]]=-1;
		for(int i=0;i<a;i++){
			if(deg[i]>mh[i]){
				req+=(deg[i]-mh[i])/2;
				add_edge(S,i,(deg[i]-mh[i])/2);
			}else if(deg[i]<mh[i]){
				add_edge(i,T,(mh[i]-deg[i])/2);
			}
		}
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)if(rev[i][j]){
			add_edge(j,i,1);
		}
		if(req==max_flow(S,T))ret++;
		for(int i=0;i<D_MAX_V;i++){
			D_G[i].clear();
			D_level[i]=D_iter[i]=0;
		}
		for(int i=0;i<a;i++)mh[i]=0;
		mh[ks[0]]=-1;
		mh[ks[1]]=1;
		req=0;
		for(int i=0;i<a;i++){
			if(deg[i]>mh[i]){
				req+=(deg[i]-mh[i])/2;
				add_edge(S,i,(deg[i]-mh[i])/2);
			}else if(deg[i]<mh[i]){
				add_edge(i,T,(mh[i]-deg[i])/2);
			}
		}
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)if(rev[i][j]){
			add_edge(j,i,1);
		}
		if(req==max_flow(S,T))ret++;
		
		printf("%d\n",ret);
	}
}

E:
解決不能。

result:
3位でした。