何問解こうが虚無に5時間を費やしたことに変わりはないセット...
B: A Cure for the Common Code
10万回見たような設定の問題...。強引に高速化した区間DPするだけ。
char in[1100]; int dp[510][510]; int lg10[510]; int kr[510][510]; int solve(int a,int b){ if(dp[a][b]!=-1)return dp[a][b]; if(a==b)return dp[a][b]=0; int ret=mod; ret=min(ret,solve(a+1,b)+1); ret=min(ret,solve(a,b-1)+1); for(int i=a+1;i<b;i++){ ret=min(ret,solve(a,i)+solve(i,b)); } for(int i=1;i<b-a;i++){ if((b-a)%i)continue; if(kr[a][i]>=b-a){ if(i>1)ret=min(ret,solve(a,a+i)+2+lg10[(b-a)/i]); else ret=min(ret,solve(a,a+i)+lg10[(b-a)/i]); } } //printf("%d %d: %d\n",a,b,ret); return dp[a][b]=ret; } int main(){ int ts=0; for(int i=1;i<510;i++){ int c=i; while(c){ lg10[i]++;c/=10; } } while(1){ scanf("%s",in); if(in[0]=='0')break; int n=strlen(in); for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){ dp[i][j]=-1; } for(int i=0;i<510;i++)for(int j=0;j<510;j++)kr[i][j]=0; for(int i=0;i<n;i++){ for(int j=1;j<=n;j++){ for(int k=i;k<n;k++){ if(k-j>=i&&in[k]!=in[k-j]){ break; } kr[i][j]++; } } } ts++; printf("Case %d: %d\n",ts,solve(0,n)); } }
D: Generalized Roman Numerals
これも強引に区間DPを高速化するだけ...setのinsertは重いのでバカみたいにやってはいけない。
char in[1100]; set<int>dp[62][62]; void calc(int a,int b){ if(a==b)return; if(dp[a][b].size())return; if(a+1==b){ if(in[a]=='I')dp[a][b].insert(1); if(in[a]=='V')dp[a][b].insert(5); if(in[a]=='X')dp[a][b].insert(10); if(in[a]=='L')dp[a][b].insert(50); if(in[a]=='C')dp[a][b].insert(100); return; } vector<int>can(5001); for(int i=a+1;i<b;i++){ calc(a,i); calc(i,b); for(set<int>::iterator it=dp[a][i].begin();it!=dp[a][i].end();it++){ for(set<int>::iterator it2=dp[i][b].begin();it2!=dp[i][b].end();it2++){ int A=*it; int B=*it2; if(A>=B)can[A+B]=1; else can[B-A]=1; } } } for(int i=0;i<5001;i++)if(can[i])dp[a][b].insert(i); } int main(){ int ts=0; while(1){ scanf("%s",in); if(in[0]=='0')break; int n=strlen(in); for(int i=0;i<62;i++)for(int j=0;j<62;j++)dp[i][j].clear(); calc(0,n); ts++; printf("Case %d:",ts); for(set<int>::iterator it=dp[0][n].begin();it!=dp[0][n].end();it++){ printf(" %d",*it); } printf("\n"); } }
A: Continued Fractions
連分数展開された有理数の四則演算をするだけ。負がある嫌がらせつき。
int p[2][20]; long long bs[2]; long long bb[2]; long long gcd(long long a,long long b){ while(a){ b%=a;swap(a,b); } return b; } void output(long long bs,long long bb){ long long g=gcd(ABS(bs),ABS(bb)); bs/=g;bb/=g; if(bb<0){ bb=-bb;bs=-bs; } vector<long long>ans; if(bs>=0){ ans.push_back(bs/bb); bs%=bb; }else{ int gb=0; while(bs<0){ gb++; bs+=bb; } ans.push_back(-gb); } while(bs){ swap(bs,bb); ans.push_back(bs/bb); bs%=bb; } for(int i=0;i<ans.size();i++){ if(i)printf(" "); printf("%I64d",ans[i]); } printf("\n"); } int main(){ int ts=0; while(1){ int a,b;scanf("%d%d",&a,&b); if(a==0)break; for(int i=0;i<a;i++){ scanf("%d",&p[0][i]); } for(int i=0;i<b;i++){ scanf("%d",&p[1][i]); } if(a>2){ bb[0]=p[0][a-1];bs[0]=1; for(int i=a-2;i>0;i--){ long long tmp=bb[0]; bb[0]=p[0][i]*bb[0]+bs[0]; bs[0]=tmp; } bs[0]+=bb[0]*p[0][0]; }else if(a==2){ bb[0]=p[0][1]; bs[0]=p[0][1]*p[0][0]+1; }else{ bb[0]=1;bs[0]=p[0][0]; } if(b>2){ bb[1]=p[1][b-1];bs[1]=1; for(int i=b-2;i>0;i--){ long long tmp=bb[1]; bb[1]=p[1][i]*bb[1]+bs[1]; bs[1]=tmp; } bs[1]+=bb[1]*p[1][0]; }else if(b==2){ bb[1]=p[1][1]; bs[1]=p[1][1]*p[1][0]+1; }else{ bb[1]=1;bs[1]=p[1][0]; } ts++; printf("Case %d:\n",ts); output(bs[0]*bb[1]+bs[1]*bb[0],bb[0]*bb[1]); output(bs[0]*bb[1]-bs[1]*bb[0],bb[0]*bb[1]); output(bs[0]*bs[1],bb[0]*bb[1]); output(bs[0]*bb[1],bb[0]*bs[1]); } }
H: Time Warp
ストレスしかたまらない算数。パソコン甲子園でやれ
char in[10]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int deg; int h; scanf("%d%s%d",°,in,&h); printf("Case %d: ",t); if(in[0]=='t'){ int nd=(360-h%12*30)-deg; while(nd<=0)nd+=360; double kr=(double)nd/5.5*60; int H=(int)(kr+0.5+EPS)/3600; int M=(int)(kr+0.5+EPS)/60%60; int S=(int)(kr+EPS+0.5)%60; H=h-H; if(M||S)H--; M=60-M; if(S)M--; if(M==60)M=0; S=60-S; if(S==60)S=0; if(H<=0)H+=12; printf("%d:%02d:%02d\n",H,M,S); }else{ int nd=deg-(360-h%12*30); while(nd<=0)nd+=360; double kr=(double)nd/5.5*60; // printf("%d %f\n",nd,kr); int H=(int)(kr+0.5+EPS)/3600; int M=(int)(kr+0.5+EPS)/60%60; int S=(int)(kr+EPS+0.5)%60; H+=h; if(H>12)H-=12; printf("%d:%02d:%02d\n",H,M,S); } } }
C: Domiyahtzee!
ただひたすらシミュレーションするだけ。やみくもに面倒なだけ。
int p[5][5]; // id int used[7][7]; int L[13]; int R[13]; int table[5][5]; int cl[5][5]; int Y=0; int dice(vector<int>v){ int ko[7]; for(int i=0;i<7;i++)ko[i]=0; for(int i=0;i<v.size();i++)ko[v[i]]++; for(int i=1;i<=6;i++){ if(ko[i]==5){ Y++; if(Y>1)return 100; return 50; } if(ko[i]==4){ return i*4; } } for(int i=1;i<=6;i++)for(int j=i+1;j<=6;j++){ if((ko[i]==3&&ko[j]==2)||(ko[i]==2&&ko[j]==3)){ return 25; } } for(int i=1;i<=6;i++){ if(ko[i]==3)return 3*i; } for(int i=1;i<=2;i++){ bool ok=true; for(int j=0;j<5;j++){ if(!ko[i+j])ok=false; } if(ok)return 40; } for(int i=1;i<=3;i++){ bool ok=true; for(int j=0;j<4;j++){ if(!ko[i+j])ok=false; } if(ok)return 30; } return 0; } int calc(){ for(int i=0;i<5;i++){ // for(int j=0;j<5;j++)printf("%d",table[i][j]); // printf("\n"); }int ret=0; Y=0; for(int i=0;i<5;i++){ vector<int>tmp; for(int j=0;j<5;j++)tmp.push_back(table[i][j]); ret+=dice(tmp); } for(int i=0;i<5;i++){ vector<int>tmp; for(int j=0;j<5;j++)tmp.push_back(table[j][i]); ret+=dice(tmp); } vector<int>tmp; for(int i=0;i<5;i++)tmp.push_back(table[i][i]); ret+=dice(tmp); for(int i=0;i<5;i++)tmp[i]=table[i][4-i]; ret+=dice(tmp); // printf("%d\n",ret); return ret; } char in[2]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int pos=0; for(int i=0;i<5;i++)for(int j=0;j<5;j++)p[i][j]=-1; for(int i=0;i<7;i++)for(int j=0;j<7;j++)used[i][j]=0; for(int i=0;i<13;i++){ while(p[pos/5][pos%5]!=-1){ pos++; } scanf("%s",in); if(in[0]=='V'){ int x,y;scanf("%d%d",&x,&y); p[pos/5][pos%5]=p[pos/5+1][pos%5]=i; table[pos/5][pos%5]=x; table[pos/5+1][pos%5]=y; L[i]=x; R[i]=y; used[min(x,y)][max(x,y)]=1; }else if(in[0]=='H'){ int x,y;scanf("%d%d",&x,&y); p[pos/5][pos%5]=p[pos/5][pos%5+1]=i; table[pos/5][pos%5]=x; table[pos/5][pos%5+1]=y; L[i]=x; R[i]=y; used[min(x,y)][max(x,y)]=1; }else{ int x;scanf("%d",&x); p[pos/5][pos%5]=i; table[pos/5][pos%5]=x; L[i]=x; R[i]=0; } } for(int i=0;i<5;i++)for(int j=0;j<5;j++)cl[i][j]=table[i][j]; int ret=calc(); for(int i=0;i<13;i++){ if(R[i]==0)continue; for(int j=1;j<7;j++)for(int k=1;k<7;k++){ if(used[j][k]||used[k][j])continue; bool fi=true; for(int m=0;m<5;m++)for(int l=0;l<5;l++){ if(p[m][l]==i){ if(fi)table[m][l]=j; else table[m][l]=k; fi=false; } } ret=max(ret,calc()); for(int m=0;m<5;m++)for(int l=0;l<5;l++)table[m][l]=cl[m][l]; } } printf("Case %d: %d\n",t,ret); } }
E: Inspectors
あの最小費用流でハミルトン路の嘘解法が作れるやつそのまま。一番楽。
int d[110][110]; int main(){ int T;scanf("%d",&T); for(int t=1;t<=T;t++){ int a;scanf("%d",&a); MCF::init(a*2+2); for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ int x;scanf("%d",&x); d[i][j]=d[j][i]=x; } } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j)continue; MCF::ae(i,j+a,1,d[i][j]); } } int S=a*2; int T=a*2+1; for(int i=0;i<a;i++){ MCF::ae(S,i,1,0); MCF::ae(a+i,T,1,0); } MCF::solve(S,T,a); printf("Case %d: %d\n",t,MCF::toc); } }
F: Path of Least Persistence
グラフだと思えばまあ普通の簡単な問題。実装量は多いけど
int dx[]={0,-1,1,0}; int dy[]={1,0,0,-1}; char ds[7]="ENSW"; int DX[110][110]; int DY[110][110]; char in[110]; int v[110][110]; int used[110][110]; int H,W; void dfs(int a,int b){ if(DX[a][b]==0&&DY[a][b]==0){ v[a][b]=0;return; } if(v[a][b]==-3){ v[a][b]=-1;return; } v[a][b]=-3; int ta=a+DX[a][b]; int tb=b+DY[a][b]; if(ta<0||ta>=H||tb<0||tb>=W){ v[a][b]=-1;return; } dfs(ta,tb); if(v[ta][tb]>=0)v[a][b]=v[ta][tb]+1; else{ v[a][b]=-1; } } int main(){ //int T;scanf("%d",&T); for(int t=1;;t++){ int a,b;scanf("%d%d",&a,&b); H=a;W=b; if(a==0)break; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(i==a-1&&j==b-1){ DX[i][j]=DY[i][j]=0; continue; } scanf("%s",in); int len=strlen(in); // printf("%s\n",in); int r; if(len==2){ r=in[0]-'0'; for(int k=0;k<4;k++)if(in[1]==ds[k]){ DX[i][j]=dx[k]*r; DY[i][j]=dy[k]*r; } }else{ r=(in[0]-'0')*10+in[1]-'0'; for(int k=0;k<4;k++)if(in[2]==ds[k]){ DX[i][j]=dx[k]*r; DY[i][j]=dy[k]*r; } } } for(int i=0;i<a;i++)for(int j=0;j<b;j++)used[i][j]=0; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ v[i][j]=-2; } } for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(v[i][j]==-2){ dfs(i,j); } } int res=v[0][0]; if(res==-1)res=mod; int ans=-1; int R=0; int C=0; int r=0; int dir=0; int nowr=0; int nowc=0; int cnt=0; while(1){ if(nowr<0||nowr>=H||nowc<0||nowc>=W)break; if(used[nowr][nowc])break; used[nowr][nowc]=1; if(nowr==a-1&&nowc==b-1)break; for(int k=1;k<100;k++)for(int l=0;l<4;l++){ int tdx=dx[l]*k; int tdy=dy[l]*k; if(tdx==DX[nowr][nowc]&&tdy==DY[nowr][nowc])continue; if(nowr+tdx<0||nowr+tdx>=a)continue; if(nowc+tdy<0||nowc+tdy>=b)continue; if(v[nowr+tdx][nowc+tdy]==-1)continue; int cost=cnt+1+v[nowr+tdx][nowc+tdy]; if(make_pair(make_pair(res,make_pair(R,C)),make_pair(r,dir))>make_pair(make_pair(cost,make_pair(nowr,nowc)),make_pair(k,l))){ res=cost;ans=1;R=nowr;C=nowc;r=k;dir=l; } } cnt++; int tor=nowr+DX[nowr][nowc]; int toc=nowc+DY[nowr][nowc]; nowr=tor;nowc=toc; } printf("Case %d: ",t); if(ans==-1){ if(res<mod)printf("none %d\n",res); else printf("impossible\n"); }else{ printf("%d %d %d%c %d\n",R,C,r,ds[dir],res); } } }
I: Watch, Man!
実 家 の よ う な 安 心 感
サ ハ 共 和 国 の 伝 統 芸 能
狼 の 習 性
共和国向け。壁がどうくっついていようがどうでもいい。壁を全列挙して交差判定してグラフ作って流すだけ。入力の仕方も心折ってくる。EPSが大きくても小さくても落ちる。
int can[110][110]; Pt gp[110]; int gl[110]; Pt ap[110]; int al[110]; Pt tmp[200]; int type[200]; Pt tang[200]; char in[2]; int main(){ //int T;scanf("%d",&T); for(int t=1;;t++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a+b+c==0)break; for(int i=0;i<110;i++)for(int j=0;j<110;j++)can[i][j]=0; vector<pair<Pt,Pt> > lseg; vector<pair<pair<Pt, double>,pair<double,double> > > cseg; for(int i=0;i<a;i++){ int n;scanf("%d",&n); for(int j=0;j<n;j++){ double X,Y; scanf("%lf%lf%s",&X,&Y,in); tmp[j]=Pt(X,Y); if(in[0]=='s')type[j]=1; else type[j]=2; if(type[j]==2){ scanf("%lf%lf",&X,&Y); tang[j]=Pt(X,Y); } } tmp[n]=tmp[0]; for(int j=0;j<n;j++){ if(type[j]==1){ lseg.push_back(make_pair(tmp[j],tmp[j+1])); }else{ Pt M1=(tmp[j]+tmp[j+1])/2; Pt M2=M1+(tmp[j+1]-tmp[j])*Pt(0,1); Pt C1=tmp[j]; Pt C2=tmp[j]+tang[j]*Pt(0,1); Pt cen=pLL(M1,M2,C1,C2); double r=(tmp[j]-cen).ABS(); double th1=(tmp[j]-cen).arg(); double th2=(tmp[j+1]-cen).arg(); if(sig((tang[j]).det(tmp[j+1]-tmp[j]))<0)swap(th1,th2); if(th1>th2){ cseg.push_back(make_pair(make_pair(cen,r),make_pair(th1,PI))); cseg.push_back(make_pair(make_pair(cen,r),make_pair(-PI,th2))); }else{ cseg.push_back(make_pair(make_pair(cen,r),make_pair(th1,th2))); } } } } //for(int i=0;i<cseg.size();i++)printf("Pt = (%f, %f), r = %f, th = [%f, %f]\n",cseg[i].first.first.x,cseg[i].first.first.y,cseg[i].first.second,cseg[i].second.first,cseg[i].second.second); for(int i=0;i<b;i++){ double X,Y; scanf("%lf%lf%d",&X,&Y,al+i); ap[i]=Pt(X,Y); } for(int i=0;i<c;i++){ double X,Y; scanf("%lf%lf%d",&X,&Y,gl+i); gp[i]=Pt(X,Y); } for(int i=0;i<b;i++)for(int j=0;j<c;j++){ Pt A=ap[i]; Pt B=gp[j]; bool ok=true; for(int k=0;k<lseg.size();k++){ if(iSS(A,B,lseg[k].first,lseg[k].second)){ok=false;break;} } if(!ok)continue; for(int k=0;k<cseg.size();k++){ double dist=dLP(A,B,cseg[k].first.first); if(dist-EPS>cseg[k].first.second)continue; pair<Pt,Pt> cro=pCL(cseg[k].first.first,cseg[k].first.second,A,B); double th1=(cro.first-cseg[k].first.first).arg(); double th2=(cro.second-cseg[k].first.first).arg(); if(iSP(A,cro.first,B)==2&&cseg[k].second.first<EPS+th1&&th1<EPS+cseg[k].second.second)ok=false; if(iSP(A,cro.second,B)==2&&cseg[k].second.first<EPS+th2&&th2<EPS+cseg[k].second.second)ok=false; } // if(ok)printf("%d %d\n",i,j); if(ok)can[i][j]=1; } for(int i=0;i<D_MAX_V;i++){ D_level[i]=D_iter[i]=0; D_G[i].clear(); } int S=b+c; int T=b+c+1; int sum=0; for(int i=0;i<b;i++){ add_edge(S,i,al[i]); sum+=al[i]; } for(int i=0;i<b;i++)for(int j=0;j<c;j++){ if(can[i][j]){ add_edge(i,b+j,1); } } for(int i=0;i<c;i++){ add_edge(b+i,T,gl[i]); } printf("Case %d: ",t); if(max_flow(S,T)==sum)printf("Yes\n"); else printf("No\n"); } }
G: 意味不明
vepifanov異常すぎるだろ
