まあそうだとは思っていたけどかなりくだらないコンテストだなあ
D: Wooden Fence
問題文をよく見ると白黒白黒...はできないらしい。
int main(){ int T;scanf("%d",&T); while(T--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c>=a/2&&b>=(a+1)/2){ printf("YES\n"); }else printf("NO\n"); } }
C: Shortest Path!
これも問題文が難しい。
int main(){ int T;scanf("%d",&T); while(T--){ int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d); double ret=0; ret+=sqrt((double)a*a+((double)b+c+c)*((double)b+c+c)); double tmp=sqrt((long long)a*a+(long long)b*b); //printf("%.12f\n",ret); ret+=tmp*d/100; //printf("%.12f\n",ret); double X=(double)b*(d)/100; double Y=(double)a*(100-d)/100; ret+=sqrt((double)Y*Y+((double)c+(b+c-X))*((double)c+(b+c-X))); printf("%.12f\n",ret); } }
F: I'm Bored!
問題文が不十分でわかりにくい。全部0やめろし
int p[30]; int main(){ int T;scanf("%d",&T); while(T--){ for(int i=0;i<26;i++)scanf("%d",p+i); int o=0; int t=0; for(int i=0;i<26;i++){ if(p[i]>=2)t++; if(p[i]==1)o++; } printf("%d ",t*2+!!o); int ret=mod; for(int i=0;i<26;i++){ if(p[i]>=2){ ret=min(ret,p[i]/2); } } if(t==0&&o==0)ret=0; if(o)ret=min(ret,o); printf("%d\n",ret); } }
H: Beautiful Substrings
まあ普通。
char S[110000]; char T[110000]; int t[26][26]; int cnt[26]; int main(){ int Test;scanf("%d",&Test); while(Test--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); scanf("%s%s",S,T); long long ret=0; for(int i=0;i<26;i++)for(int j=0;j<26;j++)t[i][j]=0; for(int i=0;i+c-1<a;i++){ t[S[i]-'a'][S[i+c-1]-'a']=1; } for(int i=0;i<26;i++)cnt[i]=0; for(int i=0;i<b;i++){ cnt[T[i]-'a']++; for(int j=0;j<26;j++){ if(t[j][T[i]-'a']){ ret+=cnt[j]; } } } printf("%I64d\n",ret); } }
K: Cyclic Shift
これも文字列bをaにするという不自然さが
char S[110000]; char T[110000]; char u[110000]; char v[110000]; int main(){ int Test;scanf("%d",&Test); while(Test--){ int a;scanf("%d",&a); scanf("%s%s",S,T); int ind=0; for(int i=0;i<a;i++){ if(S[i]!=T[i]){ u[ind]=S[i]; v[ind]=T[i]; ind++; } } if(ind==0){ printf("YES\n");continue; } bool ok=true; for(int i=0;i<ind;i++){ if(v[i]!=u[(i+1)%ind])ok=false; } if(ok)printf("YES\n");else printf("NO\n"); } }
E: Stupid Submissions
言われた通りにやる。
char in[2]; char s[11000]; int sum[11000]; int main(){ int Test;scanf("%d",&Test); while(Test--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int ret=0; for(int i=0;i<11000;i++)sum[i]=0; for(int i=0;i<a;i++){ scanf("%s",s+i); } for(int i=0;i<a;i++){ if(s[i]=='S')sum[i+1]=sum[i]+1; else sum[i+1]=sum[i]; } while(b--){ scanf("%s",in); if(in[0]=='A'){ c=a;continue; } int x;scanf("%d",&x); if(s[x-1]=='S'&&c>=x)ret++; c=max(c,x); } printf("%d\n",ret); } }
A: Multiplication Dilemma
問題文は無視する。0の個数間違えた。
int main(){ int Test;scanf("%d",&Test); while(Test--){ int a,b;scanf("%d%d",&a,&b); long long ans=(long long)a*b; bool fi=true; if(ans<0){ fi=false; printf("1000000000 x -1000000000"); ans=1000000000000000000LL+ans; } int cnt=0; while(ans){ if(ans%10){ if(!fi)printf(" + "); printf("%d",(int)(ans%10)); for(int i=0;i<cnt/2;i++)printf("0"); printf(" x "); printf("1"); for(int i=0;i<cnt-cnt/2;i++)printf("0"); fi=false; } ans/=10; cnt++; } printf("\n"); } }
J: Even Numbers
パスカルmod2を眺める。
int main(){ int Test;scanf("%d",&Test); while(Test--){ long long a;scanf("%I64d",&a); if(a<2)printf("0\n"); else{ printf("%I64d\n",a+1-(1LL<<__builtin_popcountll(a))); } } }
G: Minimax
やる。
int p[510][510]; int t[4][510][510]; int main(){ int Test;scanf("%d",&Test); while(Test--){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++)for(int j=0;j<b;j++)scanf("%d",&p[i][j]); for(int i=0;i<4;i++)for(int j=0;j<a;j++)for(int k=0;k<b;k++) t[i][j][k]=0; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ t[0][i][j]=p[i][j]; if(i)t[0][i][j]=max(t[0][i][j],t[0][i-1][j]); if(j)t[0][i][j]=max(t[0][i][j],t[0][i][j-1]); } } for(int i=0;i<a;i++){ for(int j=b-1;j>=0;j--){ t[1][i][j]=p[i][j]; if(i)t[1][i][j]=max(t[1][i][j],t[1][i-1][j]); if(j<b-1)t[1][i][j]=max(t[1][i][j],t[1][i][j+1]); } } for(int i=a-1;i>=0;i--){ for(int j=0;j<b;j++){ t[2][i][j]=p[i][j]; if(i<a-1)t[2][i][j]=max(t[2][i][j],t[2][i+1][j]); if(j)t[2][i][j]=max(t[2][i][j],t[2][i][j-1]); } } for(int i=a-1;i>=0;i--){ for(int j=b-1;j>=0;j--){ t[3][i][j]=p[i][j]; if(i<a-1)t[3][i][j]=max(t[3][i][j],t[3][i+1][j]); if(j<b-1)t[3][i][j]=max(t[3][i][j],t[3][i][j+1]); } } int ret=mod; for(int i=1;i<a-1;i++){ for(int j=1;j<b-1;j++){ int R=max(max(t[0][i-1][j-1],t[1][i-1][j+1]),max(t[2][i+1][j-1],t[3][i+1][j+1])); int L=min(min(t[0][i-1][j-1],t[1][i-1][j+1]),min(t[2][i+1][j-1],t[3][i+1][j+1])); ret=min(ret,R-L); } } printf("%d\n",ret); } }
B: Updating the Tree
ここからようやく中身がある。枝分かれがない場所で 値-深さ, 値+深さの最頻値が何回出てくるかわかればよくて、頑張ってmapで管理する。
データ間違ってると思っていろいろassertしてWAを稼いだらmap消すのの判定間違ってた(草)
int p[110000]; vector<int>g[110000]; int ans[110000]; int sz[110000]; int L[110000]; int R[110000]; map<int,int>lm; map<int,int>rm; int sh; int sc; void dfs2(int a,int b,map<int,int> &ML,map<int,int> &MR,int ordL,int ordR){ ML[L[a]+ordL]++; MR[R[a]+ordR]++; sc=max(sc,ML[L[a]+ordL]); sc=max(sc,MR[R[a]+ordR]); //printf("%d: %d %d\n",a,L[a]+ordL,R[a]+ordR); for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; dfs2(g[a][i],a,ML,MR,ordL,ordR); } } int dfs(int a,int b,int c){ int ko=0; sz[a]=1; L[a]=p[a]-c; R[a]=p[a]+c; bool dame=false; for(int i=0;i<g[a].size();i++){ if(b==g[a][i])continue; if(ko>=1){ lm.clear(); rm.clear(); sh=0; } int tmp=dfs(g[a][i],a,c+1); ko++; if(tmp==-1)dame=true; sz[a]+=sz[g[a][i]]; } if(ko>1){ lm.clear(); rm.clear(); sh=0; } if(ko>2)dame=true; if(dame)ans[a]=-1; if(ko>2||dame)return -1; if(ko==0){ ans[a]=0; lm[L[a]]++; sh=max(sh,lm[L[a]]); rm[R[a]]++; sh=max(sh,rm[R[a]]); // printf("%d: %d %d\n",a,L[a],R[a]); }else if(ko==2){ map<int,int>lc; map<int,int>rc; sc=1; lc[L[a]]=1; rc[R[a]]=1; int fi=0; for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; if(fi==0){ dfs2(g[a][i],a,lc,rc,0,0); }else{ dfs2(g[a][i],a,rc,lc,R[a]-L[a],L[a]-R[a]); } fi++; } // assert(sz[a]>=sc); ans[a]=sz[a]-sc; return -1; }else{ lm[L[a]]++; sh=max(sh,lm[L[a]]); rm[R[a]]++; sh=max(sh,rm[R[a]]); // assert(sz[a]>=sh); // assert(sz[a]>=lm.size()); ans[a]=sz[a]-sh; // printf("%d: %d %d %d\n",a,L[a],R[a],sh); } return 1; } int UF[110000]; 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 main(){ int Test;scanf("%d",&Test); while(Test--){ int a;scanf("%d",&a); for(int i=0;i<a;i++)UF[i]=-1; for(int i=0;i<a;i++)g[i].clear(); for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<a;i++)sz[i]=0; for(int i=0;i<a-1;i++){ int p,q;scanf("%d%d",&p,&q);p--;q--; g[p].push_back(q); g[q].push_back(p); UNION(p,q); } //assert(-UF[FIND(0)]==a); lm.clear(); rm.clear(); sh=sc=0; assert(lm.size()==0); assert(rm.size()==0); assert(sh==0); dfs(0,-1,0); for(int i=0;i<a;i++){ if(i)printf(" "); printf("%d",ans[i]); } printf("\n"); } }
I: Secret Project
年齢当てるカードの問題の簡易版。
long long fact[110000]; long long inv[110000]; long long finv[110000]; long long C(int a,int b){ return fact[a]*finv[b]%mod*finv[a-b]%mod; } int main(){ int Test;scanf("%d",&Test); fact[0]=finv[0]=1; inv[1]=1; for(int i=2;i<110000;i++){ inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; } for(int i=1;i<110000;i++){ fact[i]=fact[i-1]*i%mod; finv[i]=finv[i-1]*inv[i]%mod; } while(Test--){ int a,b;scanf("%d%d",&a,&b); printf("%I64d %I64d\n",C(a,a-b+1),C(a,a-b+1)*(a-b+1)%mod*inv[a]%mod); } }
まとめ:
Bが酷い
問題文が読みにくすぎる
無を身につけた
皆さんACPCで練習するのはやめましょう。
