PCK2014本選の問題が今までFrameしかなかったが、最近他も追加されたので全部解いた。
0305: Yuekis' Audio Room
やるだけ。
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a;scanf("%d",&a); while(a--){ int r,t; scanf("%d%d",&r,&t); if(r%100==0){ if(t%30==0){ printf("%d\n",t/30*5+r/100); }else{ printf("%d %d\n",r/100+t/30*5,r/100+t/30*5+5); } }else{ if(t%30==0){ printf("%d %d\n",r/100+t/30*5,r/100+1+t/30*5); }else{ printf("%d %d %d %d\n",r/100+t/30*5,r/100+1+t/30*5,r/100+t/30*5+5,r/100+1+t/30*5+5); } } } }
0306: Symmetric Ternary Number
全探索。
#include<stdio.h> #include<algorithm> using namespace std; int p3[13]; int main(){ int a;scanf("%d",&a); p3[0]=1; for(int i=1;i<13;i++)p3[i]=p3[i-1]*3; for(int i=0;i<p3[12];i++){ int cur=0; for(int j=0;j<12;j++){ if(i/p3[j]%3==1)cur+=p3[j]; if(i/p3[j]%3==2)cur-=p3[j]; } if(cur==a){ bool ok=false; for(int j=11;j>=0;j--){ if(!ok&&i/p3[j]%3==0)continue; if(i/p3[j]%3==0)printf("0"); if(i/p3[j]%3==1)printf("+"); if(i/p3[j]%3==2)printf("-"); ok=true; } printf("\n"); break; } } }
0307: Nisshinkan Marathon Club
問題文が意味不明。シミュレーション的なのをやれ、という意味らしい。
#include<stdio.h> #include<algorithm> using namespace std; int p[110]; int rem[1100]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++)scanf("%d",p+i); int ret=0; for(int i=0;i<c;i++){ for(int j=0;j<a;j++){ if(rem[(i+1)*p[j]%b]==0){ ret++; }else rem[(i+1)*p[j]%b]--; } if(i){ for(int j=0;j<a;j++){ rem[(i+1)*p[j]%b]++; } } } printf("%d\n",ret); }
0308: Deadlock
概念がいまいち理解できてないしちゃんと考えてないけどどうせ閉路判定と思って書いたら通った。
ICPCでもデッドロックの問題は何回か出たが、問題文の概念が理解できないので毎回他の人に任せている。もうちょっと問題文を定式化してほしい。
#include<stdio.h> #include<algorithm> using namespace std; int g[210][210]; char in[10]; int main(){ int a;scanf("%d",&a); for(int i=0;i<200;i++)g[i][i]=1; for(int i=0;i<a;i++){ int p,q;scanf("%d%s%d",&p,in,&q); p--;q--; if(in[0]=='l')g[p][q+100]=1; else g[q+100][p]=1; } for(int k=0;k<200;k++)for(int i=0;i<200;i++)for(int j=0;j<200;j++){ if(g[i][k]&&g[k][j])g[i][j]=1; } for(int i=0;i<200;i++)for(int j=i+1;j<200;j++){ if(g[i][j]&&g[j][i]){printf("1\n");return 0;} } printf("0\n"); }
0309: New Drug Development
見ての通り木DP。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; char str[1100][5]; long long mod=1000000007; vector<int>g[1100]; long long dp[1100]; long long calc(int a){ for(int i=0;i<g[a].size();i++)calc(g[a][i]); if(str[a][0]=='E'){ long long ret=1; for(int i=0;i<g[a].size();i++)ret=ret*dp[g[a][i]]%mod; if(str[a][1]=='?')ret=(ret+1)%mod; return dp[a]=ret; } if(str[a][0]=='R'){ long long ret=1; for(int i=0;i<g[a].size();i++)ret=ret*(dp[g[a][i]]+1)%mod; if(str[a][1]!='?')ret=(ret+mod-1)%mod; return dp[a]=ret; } long long ret=0; for(int i=0;i<g[a].size();i++)ret=(ret+dp[g[a][i]])%mod; if(str[a][1]=='?')ret=(ret+1)%mod; return dp[a]=ret; } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%s",str[i]); } for(int i=0;i<a-1;i++){ int s,t;scanf("%d%d",&s,&t);s--;t--; g[s].push_back(t); } printf("%lld\n",calc(0)); //for(int i=0;i<a;i++)printf("%lld\n",dp[i]); }
0310: Frame
昔解いたやつ。累積和でうんたらかんたら
#include<stdio.h> #include<algorithm> using namespace std; int b[400][400]; int sum[400][400]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)for(int j=0;j<a;j++)scanf("%d",&b[i][j]); for(int i=0;i<a;i++)for(int j=0;j<a;j++) sum[i+1][j+1]=b[i][j]; for(int i=0;i<=a;i++)for(int j=1;j<=a;j++){ sum[i][j]+=sum[i][j-1]; } for(int i=0;i<=a;i++)for(int j=1;j<=a;j++){ sum[j][i]+=sum[j-1][i]; } int ret=-999999999; for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ int L=-999999999; int tmp=0; for(int k=0;k<a;k++){ ret=max(ret,sum[j+1][k+1]-sum[j+1][k]-sum[i][k+1]+sum[i][k]+tmp+L); L=max(L,sum[j][k+1]-sum[j][k]-sum[i+1][k+1]+sum[i+1][k]-tmp); tmp+=b[i][k]; tmp+=b[j][k]; } } } for(int i=0;i<a;i++){ int now=0; for(int j=0;j<a;j++){ now+=b[i][j]; if(now<0)now=0; ret=max(ret,now); } } for(int i=0;i<a;i++){ int now=0; for(int j=0;j<a;j++){ now+=b[j][i]; if(now<0)now=0; ret=max(ret,now); } } printf("%d\n",ret); }
0311: Kaguya
空間幾何。許容誤差が大きいので小さく区切って個数カウント。
月の座標、かぐやの座標を計算し、月の中心と「かぐや-地球の中心」間の線分との距離を求める。
これは面倒で有名なので三分探索。ソースは1KBを越えなかった。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; double PI=acos(-1.0); int main(){ int a,b; scanf("%d%d",&a,&b); int c=b*100; int ret=0; for(int i=0;i<c;i++){ double t=0.005+(double)i/100; double tm=(double)a*PI/180+PI*2*t*60/2500000; double mx=cos(tm)*380000; double my=sin(tm)*380000; double tv=PI/2+PI*2*t/120; double vx=cos(tv)*1900; double vz=sin(tv)*1900; double px=mx+vx; double py=my; double pz=vz; // printf("%f %f %f\n",px,py,pz); double left=0; double right=1; bool ok=false; for(int j=0;j<50;j++){ double m1=(left+left+right)/3; double m2=(left+right+right)/3; double d1=sqrt((px*m1-mx)*(px*m1-mx)+(py*m1-my)*(py*m1-my)+(pz*m1)*(pz*m1)); double d2=sqrt((px*m2-mx)*(px*m2-mx)+(py*m2-my)*(py*m2-my)+(pz*m2)*(pz*m2)); if(d1<d2)right=m2; else left=m1; if(min(d1,d2)<1800)ok=true; } if(ok)ret++; } printf("%.2f\n",(double)ret/100); }
0312: Net Cafe
bitDPするだけ。
#include<stdio.h> #include<algorithm> using namespace std; int s[210000]; int t[210000]; int c[20]; int d[20]; int p[210000]; int q[210000]; int dp[1<<15]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d%d",p+i,q+i); s[i+1]=s[i]+p[i]; t[i+1]=t[i]+q[i]; } for(int i=0;i<b;i++)scanf("%d%d",c+i,d+i); for(int i=0;i<(1<<b);i++)dp[i]=-999999999; dp[0]=0; for(int i=0;i<(1<<b);i++){ for(int j=0;j<b;j++){ if(i&(1<<j))continue; int to=min(upper_bound(s,s+a+1,s[dp[i]]+c[j])-s-1,upper_bound(t,t+a+1,t[dp[i]]+d[j])-t-1); dp[i+(1<<j)]=max(dp[i+(1<<j)],to); } } printf("%d\n",dp[(1<<b)-1]); }
0313: Unknown Germ
一番難しい、というかややこしい。
長さを2ずつ縮めていくが、縮めたい場所を外に出すまでちまちまrotateしていく。
これをいかにコードにするかが本質。チーム戦ならではの問題だと思う。(もう1人が他の実装をしている間にでも方法を1つ1つ書きならべていく)
#include<stdio.h> #include<algorithm> #include<string.h> #include<vector> #include<string> using namespace std; char str[110]; struct wolf{ int type; int num; int at; wolf(int a,int b,int c){ type=a;num=b;at=c; } wolf(){type=num=at=0;} }; int sz; vector<wolf>v; int t[210]; int main(){ int a;scanf("%d",&a); while(a--){ scanf("%s",str); int m=0; int b=0; int n=strlen(str); for(int i=0;str[i];i++){ if(str[i]=='o')m++; else b++; } if(m<b){ printf("-1\n");continue; } if(m==b){ int now=0; bool ok=true; for(int i=0;str[i];i++){ if(str[i]=='o')now++; else now--; if(now==2||now==-2)ok=false; } if(!ok){ printf("-1\n"); }else{ printf("%d\n",n/2-1); for(int i=0;i<n/2-1;i++){ printf("split %d %d\n",i*2,1); } } continue; } sz=1; v.clear(); string now=str; int s=0; while(now.size()>2){ // printf("%s ",now.c_str());fflush(stdout); bool ow=true; for(int i=0;i<now.size();i++){ if(now[i]=='x')ow=false; } if(ow){ v.push_back(wolf(1,s,0)); s=sz; sz++; now=now.substr(1); continue; } for(int i=0;i<now.size()-1;i++){ if(now[i]=='o'&&now[i+1]=='o')continue; if(now[i]=='x'&&now[i+1]=='x')continue; int V=0; for(int j=0;j<i;j++){ if(now[j]=='o')V++; else V--; } if(i==0){ v.push_back(wolf(1,s,1)); s=sz+1; sz+=2; now=now.substr(2); break; } if(i==now.size()-2){ v.push_back(wolf(1,s,now.size()-3)); s=sz; sz+=2; now=now.substr(0,now.size()-2); break; } // printf("%d %d\n",i,V);fflush(stdout); if(V>=0){ for(int j=0;j<110;j++)t[j]=-1; int dep=0; for(int j=0;j<i;j++){ if(now[j]=='o')dep++; else dep--; if(dep>=0)t[dep]=j; } int rot=0; for(int j=0;j<=V;j++){ if(t[j]==-1)continue; v.push_back(wolf(1,s,t[j]-rot)); v.push_back(wolf(2,sz+1,sz)); s=sz+2; sz+=3; now=now.substr(t[j]-rot+1)+now.substr(0,t[j]-rot+1); rot=t[j]+1; } v.push_back(wolf(1,s,1)); now=now.substr(2); s=sz+1; sz+=2; }else{ V=0; for(int j=i+2;j<now.size();j++){ if(now[j]=='o')V++; else V--; } for(int j=0;j<110;j++)t[j]=-1; int dep=0; for(int j=now.size()-1;j>i+1;j--){ if(now[j]=='o')dep++; else dep--; if(dep>=0)t[dep]=j; } int rot=0; for(int j=0;j<=V;j++){ if(t[j]==-1)continue; // printf("%d %d %d\n",s,t[j],t[j]+rot);fflush(stdout); v.push_back(wolf(1,s,t[j]-1+rot)); v.push_back(wolf(2,sz+1,sz)); s=sz+2; sz+=3; now=now.substr(t[j]+rot)+now.substr(0,t[j]+rot); rot=now.size()-t[j]; } v.push_back(wolf(1,s,now.size()-3)); now=now.substr(0,now.size()-2); s=sz; sz+=2; } break; } } printf("%d\n",v.size()); for(int i=0;i<v.size();i++){ if(v[i].type==1)printf("split "); else printf("join "); printf("%d %d\n",v[i].num,v[i].at); } } }
0314: The Kingdom of Akabeko
問題文の通りに行列木で数えるだけ。最後の割りにかなり素直。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; long long mod=1000000007; int g[110][110]; pair<int,pair<int,int> > edge[11000]; int UF[110]; 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 conv[110]; int ind[110]; vector<int>v[10]; long long getinv(long long a){ long long ret=1; int t=mod-2; while(t){ if(t%2)ret=ret*a%mod; a=a*a%mod; t/=2; } return ret; } long long mat[110][110]; long long calc(vector<int>p){ int n=p.size(); for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0; for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){ if(g[p[i]][p[j]]){ mat[i][j]=mat[j][i]=mod-1; mat[i][i]++; mat[j][j]++; } } //for(int i=0;i<n-1;i++){ // for(int j=0;j<n-1;j++)printf("%lld ",mat[i][j]); // printf("\n"); //} long long ret=1; for(int i=0;i<n-1;i++){ int at=-1; for(int j=i;j<n-1;j++){ if(mat[j][i]){ at=j;break; } } if(!~at)return 0; if(at!=i)ret=(mod-ret)%mod; for(int j=0;j<n-1;j++)swap(mat[at][j],mat[i][j]); ret=ret*mat[i][i]%mod; long long ks=getinv(mat[i][i]); for(int j=0;j<n-1;j++)mat[i][j]=mat[i][j]*ks%mod; for(int j=i+1;j<n-1;j++){ long long tmp=mat[j][i]; for(int k=0;k<n-1;k++)mat[j][k]=(mat[j][k]+mod-tmp*mat[i][k]%mod)%mod; } } return ret; } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int p,q,r; scanf("%d%d%d",&p,&q,&r); p--;q--; g[p][q]=g[q][p]=1; edge[i]=make_pair(r,make_pair(p,q)); } std::sort(edge,edge+b); for(int i=0;i<a;i++)UF[i]=-1; int dist=0; for(int i=0;i<b;i++){ UNION(edge[i].second.first,edge[i].second.second); if(UF[FIND(0)]==-a){ dist=edge[i].first;break; } } for(int i=0;i<a;i++)UF[i]=-1; for(int i=0;i<b;i++){ if(dist>edge[i].first)UNION(edge[i].second.first,edge[i].second.second); } int n=0; for(int i=0;i<a;i++)if(UF[i]<0)conv[i]=n++; for(int i=0;i<a;i++)if(UF[i]>=0)conv[i]=conv[FIND(i)]; for(int i=0;i<a;i++){ ind[i]=v[conv[i]].size(); v[conv[i]].push_back(i); } //for(int i=0;i<a;i++)printf("%d\n",conv[i]); long long ret=0; for(int i=0;i<(1<<n);i++){ if(i==0||i==(1<<n)-1)continue; vector<int>L; vector<int>R; for(int j=0;j<a;j++){ if(i&(1<<(conv[j])))L.push_back(j); else R.push_back(j); } ret=(ret+calc(L)*calc(R))%mod; } printf("%d %lld\n",dist,ret); }
