CTPC
書かないといけない大会の記事がたまってきました。
CTPC。試験初日にありました。適当に参加してゆっくりと全完したらゆっくりした人向け順位になった(3位)。あと少しFをとりあえず投げてればなぜか通って2位だったが、まあいいことにする。
A - Average
さすがにやるだけ
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); printf("%s\n",a+b+c+d+max(max(a,b),max(c,d))>=300?"Yes":"No"); }
B - Macaron
いつしかのJOI予選3と全く同じことをするだけで解ける。First Acceptanceらしい。要出典
#include<stdio.h> #include<algorithm> using namespace std; int abs(int a){return a<0?-a:a;} int out[50][50]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ int d,e,f; scanf("%d%d%d",&d,&e,&f); f++; for(int j=0;j<a;j++) for(int k=0;k<b;k++) if((max(abs(d-j),abs(e-k))+1)%f==0)out[j][k]++; } for(int i=0;i<b;i++,printf("\n")) for(int j=0;j<a;j++) printf("%c",out[j][i]&1?'#':'.'); }
C - Communication Tool
文字列。気をつけるところがたくさんある(0文字とか)。こんな複雑な入力C++でやる能力を持ち合わせてないので、普通にJava.
import java.util.*; class Main{ public static void main(String[] args){ Scanner s=new Scanner(System.in); int a=s.nextInt(); int b=0; int c=0; s.nextLine(); for(int i=0;i<a;i++){ String str=s.nextLine(); if(1<=str.length()&&str.length()<=140){ if(str.charAt(0)=='@')b++; else c++; } } if(b==0&&c==0)System.out.println("Tweet:NA Reply:NA"); else System.out.printf("Tweet:%d Reply:%d\n",c*100/(b+c),b*100/(b+c)); } }
K - Prime Factorial
適当にふるいをしているときに掛け算して可能なものテーブルを処理していく。
#include<stdio.h> #include<algorithm> using namespace std; bool ok[1000001]; int p[10000001]; int main(){ p[0]=p[1]=-1; long long now=1; ok[1]=true; for(int i=2;i<=10000000;i++){ if(p[i]==0){ p[i]=1; for(int j=i+i;j<=10000000;j+=i)p[j]=-1; now=now*i%1000000; ok[(int)now]=true; } } int a; scanf("%d",&a); for(int i=0;i<a;i++){ int b; scanf("%d",&b); printf("%s\n",ok[b]?"Yes":"No"); } }
H - Magical Jump
サイズが小さいので自明なDPをするだけで通ってしまう。本来はもっと制約厳しい予定だったようだ。
#include<stdio.h> #include<queue> using namespace std; int dp[50][21][21]; bool wolf[21][21]; bool mawari[21][21]; int dx[]={1,1,1,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,-1,0,1,-1}; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ int d,e; scanf("%d%d",&d,&e); wolf[d][e]=true; for(int j=0;j<8;j++){ if(0<=d+dx[j]&&d+dx[j]<=a&&0<=e+dy[j]&&e+dy[j]<=b)mawari[d+dx[j]][e+dy[j]]=true; } } dp[0][0][0]=1; int MOD=1000000; for(int i=0;;i++){ if(dp[i][a][b]){ printf("%d\n",dp[i][a][b]); break; } for(int j=0;j<=a;j++){ for(int k=0;k<=b;k++){ if(j!=a&&k!=b&&!mawari[j][k]&&!wolf[j+1][k+1])dp[i+1][j+1][k+1]=(dp[i+1][j+1][k+1]+dp[i][j][k])%MOD; if(j!=a&&!wolf[j+1][k])dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k])%MOD; if(k!=b&&!wolf[j][k+1])dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k])%MOD; } } } }
G - Lucky Number
2進数っぽく適当に処理してやる。
#include<stdio.h> int ad[50]; int main(){ ad[0]=1; for(int i=1;i<50;i++)ad[i]=ad[i-1]*7%1000000; int a; scanf("%d",&a); int ret=0; int at=0; while(a){ if(a%2)ret+=ad[at]; at++; a/=2; } printf("%d\n",ret%1000000); }
E - Airport
やたらとNが小さい。頭悪いので直感的に強連結成分分解を書いたが、WFでいける。
どうやら手元の強連結成分分解のライブラリはまるっきり合ってないらしい。
#include<stdio.h> #include<map> #include<vector> #include<algorithm> #include<string> using namespace std; int mat[17][17]; map<string,int> m; char str[32]; vector<int> g[500]; vector<int> rev[500]; vector<vector<int> >scc; int dp[500]; bool v[500]; int now=0; void dfs(int a){ if(v[a])return; v[a]=true; for(int i=0;i<g[a].size();i++){ dfs(g[a][i]); } dp[now++]=a; } vector<int> p; void DFS(int a){ p.push_back(a); v[a]=true; for(int i=0;i<rev[a].size();i++){ if(!v[rev[a][i]])DFS(rev[a][i]); } } int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%s",str); string name=str; m[name]=i; } int b; scanf("%d",&b); for(int i=0;i<b;i++){ scanf("%s",str); string A=str; scanf("%s",str); string B=str; mat[m[A]][m[B]]=1; } bool ok=true; for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ if(mat[i][j]&&mat[j][i])ok=false; if(!mat[i][j]&&!mat[j][i])ok=false; if(mat[i][j]){ g[i].push_back(j); rev[j].push_back(i); } if(mat[j][i]){ g[j].push_back(i); rev[i].push_back(j); } } } if(ok==false){ printf("No\n"); return 0; } for(int i=0;i<a;i++){ dp[i]=-1; v[i]=false; } for(int i=0;i<a;i++)dfs(i); for(int i=0;i<a;i++)v[i]=false; for(int i=a-1;i>=0;i--){ if(!v[dp[i]]){ p.clear(); DFS(dp[i]); scc.push_back(p); } } if(scc.size()!=1)ok=false; printf("%s\n",ok?"Yes":"No"); }
D - Knapsack Problem
2回もWAを出している…
クエリ数が少ないので、クエリで変わるものだけ特別にもっていて、そこだけ毎回のクエリのときに変更してやる。なぜこれがDのところにあるのだろう。
#include<stdio.h> #include<algorithm> using namespace std; int dp[3001][10001]; bool t[3000]; int q1[300],q2[300],q3[300],q4[300]; int w[3000]; int v[3000]; int dp2[31][10001]; int list[30]; int main(){ int a,b; int at=0; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d%d",w+i,v+i); } for(int i=0;i<b;i++){ scanf("%d%d",q1+i,q2+i); if(q1[i]==1){ scanf("%d%d",q3+i,q4+i); t[q2[i]-1]=true; bool ad=true; for(int j=0;j<at;j++)if(list[j]==q2[i]-1)ad=false; if(ad)list[at++]=q2[i]-1; } } for(int i=0;i<=a;i++){ for(int j=0;j<=10000;j++){ if(j<10000)dp[i][j+1]=max(dp[i][j],dp[i][j+1]); if(i==a)continue; if(j+w[i]<=10000&&!t[i]){ dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]); } dp[i+1][j]=max(dp[i+1][j],dp[i][j]); } } for(int i=0;i<=at;i++){ for(int j=0;j<=10000;j++){ if(j<10000)dp2[i][j+1]=max(dp2[i][j],dp2[i][j+1]); if(i==at)continue; if(j+w[list[i]]<=10000){ dp2[i+1][j+w[list[i]]]=max(dp2[i+1][j+w[list[i]]],dp2[i][j]+v[list[i]]); } dp2[i+1][j]=max(dp2[i+1][j],dp2[i][j]); } } for(int i=0;i<b;i++){ if(q1[i]==0){ int ret=0; for(int j=0;j<=q2[i];j++){ ret=max(ret,dp[a][j]+dp2[at][q2[i]-j]); // printf("%d %d\n",dp[a][j],dp2[at][q2[i]-j]); } printf("%d\n",ret); }else{ w[q2[i]-1]=q3[i]; v[q2[i]-1]=q4[i]; for(int j=0;j<=at;j++) for(int k=0;k<=10000;k++) dp2[j][k]=0; for(int k=0;k<=at;k++){ for(int j=0;j<=10000;j++){ if(j<10000)dp2[k][j+1]=max(dp2[k][j],dp2[k][j+1]); if(k==at)continue; if(j+w[list[k]]<=10000){ dp2[k+1][j+w[list[k]]]=max(dp2[k+1][j+w[list[k]]],dp2[k][j]+v[list[k]]); } dp2[k+1][j]=max(dp2[k+1][j],dp2[k][j]); } } } } }
I - Card Game
よく考えるとGreedyっぽい要素を含んだDPになる。もっと早く気づくべきかなあ
#include<stdio.h> #include<algorithm> using namespace std; int perm[5]; char str[100001]; char w[6]; int dp[100001][5]; int main(){ int a,b; scanf("%d%s%d%s",&a,w,&b,str); for(int i=0;i<a;i++){ perm[i]=i; } int ret=0; do{ for(int i=0;i<100001;i++) for(int j=0;j<5;j++) dp[i][j]=0; for(int i=0;i<b;i++){ for(int j=0;j<a;j++)dp[i+1][j]=dp[i][j]; if(w[perm[0]]==str[i]){ dp[i+1][0]=dp[i][0]+1; } for(int j=1;j<a;j++){ if(w[perm[j]]==str[i]){ dp[i+1][j]=min(dp[i][j]+1,dp[i][j-1]); } } } ret=max(ret,dp[b][a-1]); }while(next_permutation(perm,perm+a)); printf("%d\n",ret); }
J - Favorite Number
40000くらいまでは2乗する見込みがあるのでそこまでは真面目に探索、あとは差とって適当で通る。
#include<stdio.h> #include<algorithm> #include<queue> using namespace std; int b[11]; int mat[11][11]; int bfs[50000]; int Abs(int a){ return a<0?-a:a; } int calc(int p,int q){ int dist=Abs(p-q); if(dist%3==0){ return dist/3; } if(dist%3==1){ if(dist==1)return 2; return dist/3+1; } if(dist%3==2){ return dist/3+1; } } long long dp[11][1<<11]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d",b+i); } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ mat[i][j]=calc(b[i],b[j]); if(b[i]<50000){ queue<int>Q; for(int k=0;k<50000;k++){ bfs[k]=-1; } bfs[b[i]]=0; Q.push(b[i]); while(Q.size()){ int at=Q.front(); Q.pop(); if((long long)at*at<50000LL&&bfs[at*at]==-1){ bfs[at*at]=bfs[at]+1; Q.push(at*at); } if(at-3>=0&&bfs[at-3]==-1){ bfs[at-3]=bfs[at]+1; Q.push(at-3); } if(at+3<50000&&bfs[at+3]==-1){ bfs[at+3]=bfs[at]+1; Q.push(at+3); } if(at-2>=0&&bfs[at-2]==-1){ bfs[at-2]=bfs[at]+1; Q.push(at-2); } if(at+2<50000&&bfs[at+2]==-1){ bfs[at+2]=bfs[at]+1; Q.push(at+2); } } for(int k=0;k<45000;k++){ mat[i][j]=min(mat[i][j],bfs[k]+calc(k*k,b[j])+1); } }else{ for(int k=0;k<45000;k++){ mat[i][j]=min(mat[i][j],calc(b[i],k)+calc(k*k,b[j])+1); } } } } for(int i=0;i<11;i++) for(int j=0;j<(1<<11);j++) dp[i][j]=9999999999999999LL; for(int i=0;i<a;i++) dp[i][1<<i]=0; for(int i=0;i<(1<<a);i++){ for(int j=0;j<a;j++){ for(int k=0;k<a;k++){ dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+mat[j][k]); } } } //for(int i=0;i<a;i++,printf("\n")) // for(int j=0;j<a;j++) // printf("%d ",mat[i][j]); long long ret=9999999999999999LL; for(int i=0;i<a;i++)ret=min(ret,dp[i][(1<<a)-1]); printf("%lld\n",ret); }
F - Night Museum
なかなか難しい問題。どうやら誤差が激甘らしい。適当に二分探索＋平面走査をした。想定解法も変な解法なので、どの解法が一番精度出るかはよくわからない。
ちなみにこのコードはあるケースにおいてWAします。がんばって見つけてください(テストケースのおかげで通ったとも、WAするケースがあまりに微妙だったために通ったとも言える)
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; int x[20]; int y[20]; double event[1000]; pair<double,int> p[1000]; double Abs(double a){ return a<0.0?-a:a; } int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ scanf("%d%d",x+i,y+i); } double left=0; double right=2000; for(int i=0;i<50;i++){ double M=(left+right)/2; //M=710; // printf("%f\n",M); int at=0; for(int j=0;j<c;j++){ for(int k=j+1;k<c;k++){ double d=sqrt((y[j]-y[k])*(y[j]-y[k])+(x[j]-x[k])*(x[j]-x[k])); // printf("%f %f\n",d,M); if(M>d/2&&d>0.00000001){ double e=sqrt(M*M-d*d/4); event[at++]=(double)(y[j]+y[k])/2+e*((double)(x[k]-x[j])/d); event[at++]=(double)(y[j]+y[k])/2-e*((double)(x[k]-x[j])/d); } } event[at++]=(double)y[j]; } event[at++]=0; event[at++]=b; std::sort(event,event+at); bool ok=true; for(int j=0;j<at;j++){ // printf("%f\n",event[j]); if(event[j]<-0.000001||event[j]>b+0.0000001)continue; int now=0; for(int k=0;k<c;k++){ double q=Abs(event[j]-(double)y[k]); if(q>M)continue; double h=sqrt(M*M-q*q); p[now++]=make_pair((double)x[k]-h,1); p[now++]=make_pair((double)x[k]+h,0); } p[now++]=make_pair(0.000001,2); p[now++]=make_pair((double)a-0.000001,2); std::sort(p,p+now); int ap=0; for(int k=0;k<now;k++){ if(p[k].second==1)ap++; else if(p[k].second==0)ap--; if(-0.0000001<=p[k].first&&p[k].first<=(double)a+0.0000001&&ap==0)ok=false; } } if(ok)right=M; else left=M; } printf("%f\n",right); }
まとめ
全完到達時刻がめちゃくちゃ遅かったのにそれまでが早かったので順位が何とかなってしまいました。k_yuridenamidaの正体を知って驚いている。
