tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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するだけなんですか...たまげたなぁ。