Yandex 2018 Qual
バーチャルをまたやった。
A: 本番もといた。
int b[110]; int main(){ for(int i=0;i<10;i++){ int p;scanf("%d",&p);b[p]++; } int t;scanf("%d",&t); while(t--){ int ret=0; for(int i=0;i<6;i++){ int p;scanf("%d",&p);ret+=b[p]; } if(ret>=3)printf("Lucky\n"); else printf("Unlucky\n"); } }
B: これは頑張るとしか言いようがない。
int p[300][300]; int ans[11000]; int ad[11000]; int at[11000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a*2;i++){ for(int j=0;j<a;j++){ scanf("%d",&p[i][j]); ad[p[i][j]]+=j; } } for(int i=0;i<11000;i++)at[i]=-1; for(int i=1;i<=a*a;i++){ if(ad[i]==0){ int nt=0; for(int j=0;j<a*2;j++){ if(p[j][0]==i){ nt=j; for(int k=0;k<a;k++){ ans[k]=p[j][k]; at[p[j][k]]=k; } break; } } for(int j=0;j<a*2;j++){ if(nt==j)continue; if(~at[p[j][0]]){ for(int k=0;k<a;k++){ ans[at[p[j][0]]+k*a]=p[j][k]; } } } break; } } for(int i=0;i<a*a;i++){ if(i)printf(" "); printf("%d",ans[i]); }printf("\n"); }
C: a^((a-1)^2).
long long pw(long long a,long long b){ long long ret=1; while(b){ if(b%2)ret=ret*a%mod; a=a*a%mod; b/=2; } return ret; } int main(){ int a;scanf("%d",&a); printf("%d\n",(int)pw(a,(a-1)*(a-1))); }
D: n個の棒で三角形が全く作れないように頑張ると長さの下界がO(Fib(n))になる話
long long p[310000]; pair<long long,int> q[310]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%I64d",p+i); } while(b--){ int l,r;scanf("%d%d",&l,&r);l--;r--; if(r-l+1<3){ printf("-1\n");continue; } int sz=0; for(int i=l;i<=r;i++){ if(sz==100)break; q[sz++]=make_pair(p[i],i+1); } std::sort(q,q+sz); bool ok=false; for(int i=0;i<sz-2;i++){ if(q[i].first+q[i+1].first>q[i+2].first){ printf("%d %d %d\n",q[i].second,q[i+1].second,q[i+2].second); ok=true;break; } } if(!ok)printf("-1\n"); } }
E: しゃくとりするだけ
char in[20]; long long p[110000]; long long q[110000]; map<long long,int> m; int tmp[110000]; int fla=0; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%s",in); long long cur=0; for(int j=0;in[j];j++){ cur*=27; cur+=in[j]-'a'+1; } p[i]=cur; } for(int i=0;i<b;i++){ scanf("%s",in); long long cur=0; for(int j=0;in[j];j++){ cur*=27; cur+=in[j]-'a'+1; } q[i]=cur; } for(int i=0;i<b;i++){ m[q[i]]=i; } long long ret=0; int at=-1; for(int i=0;i<a;i++){ while(at<a&&fla<b){ at++; if(at==a)break; if(m.count(p[at])==0)continue; tmp[m[p[at]]]++; if(tmp[m[p[at]]]==1)fla++; } ret+=a-at; if(m.count(p[i])){ tmp[m[p[i]]]--; if(tmp[m[p[i]]]==0)fla--; } } printf("%I64d\n",ret); }
F: は? と思ったけどこれ普通にDPするだけなんですか...たまげたなぁ。