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位でした。
