JOI模擬予選 by snuke - tozangezan's diary

こんな問題セットでこの成績はまずいでしょ。

1.やるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",a-b+c-d);
	return 0;
}

2.やるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
char a[1024];
char b[1024];
int main(){
	int c;
	scanf("%d%s%s",&c,a,b);
	int ret=0;
	for(int i=0;i<c;i++){
		int count=0;
		for(int j=0;j<c;j++)if(a[j]==b[(i+j)%c])count++;
		ret=max(ret,count);
	}
	printf("%d\n",ret);
	return 0;
}

3.左から決めていく。表示されるのが遅かったのでほげ

#include<stdio.h>
int dat[1000][1000];
int ans[1000][1000];
int dx[]={1,1,0,0,0,-1,-1,-1};
int dy[]={0,-1,1,0,-1,1,0,-1};
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++)
		for(int j=0;j<a;j++)
			scanf("%d",&dat[i][j]);
	for(int i=0;i<b-2;i++){
		for(int j=0;j<a-1;j++){
			int p=dat[i][j];
			for(int k=0;k<8;k++){
				if(0<=i+dx[k]&&i+dx[k]<b&&0<=j+dy[k]&&j+dy[k]<a)p-=ans[i+dx[k]][j+dy[k]];
			}
			ans[i+1][j+1]=p;
		}
	}
	for(int i=0;i<b;i++){
		for(int j=0;j<a;j++){
			if(j)printf(" ");
			printf("%d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}

4.DP。この形は始めて見たけど。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dat[100000];
int dp[100000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	c--;
	for(int i=0;i<b;i++){
		scanf("%d",dat+i);
		dat[i]--;
	}
	for(int i=0;i<100000;i++)dp[i]=-99999999;
	dp[c]=0;
	for(int i=0;i<b;i++){
		int k=max(dp[dat[i]],dp[dat[i]+1]+1);
		dp[dat[i]+1]=max(dp[dat[i]+1],dp[dat[i]]+1);
		dp[dat[i]]=k;
	}
	printf("%d\n",dp[0]);
	return 0;
}

5.BFSするだけ

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int to[10000][10];
int bfs[10000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		for(int j=0;j<b;j++){
			scanf("%d",&to[i][j]);
			to[i][j]--;
		}
	}
	for(int i=0;i<a;i++)bfs[i]=99999999;
	bfs[0]=0;
	queue<int> Q;
	Q.push(0);
	while(Q.size()){
		int at=Q.front();
		if(at==a-1)break;
		Q.pop();
		for(int i=0;i<b;i++){
			if(bfs[to[at][i]]==99999999){
				bfs[to[at][i]]=bfs[at]+1;
				Q.push(to[at][i]);
			}
		}
		if(bfs[at+1]==99999999){
			bfs[at+1]=bfs[at]+1;
			Q.push(at+1);
		}
	}
	printf("%d\n",bfs[a-1]);
	return 0;
}

6.むずかしそうだけど適当なコードを書けば通るらしい。*は-より先に計算されるので、これをミスるとWAをもらってしまう。

#include<stdio.h>
#include<algorithm>
using namespace std;
int R[1000];
int C[1000];
bool p[1000001];
bool q[1000001];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",R+i);
		if(R[i]>a*b||p[R[i]]){
			printf("0\n");
			return 0;
		}
		p[R[i]]=true;
	}
	std::sort(R,R+a);
	for(int j=0;j<b;j++){
		scanf("%d",C+j);
		if(C[j]>a*b||q[C[j]]){
			printf("0\n");
			return 0;
		}
		q[C[j]]=true;
	}
	long long MOD=1000000007;
	std::sort(C,C+b);
	long long ret=1;
	for(int i=a*b;i>0;i--){
		if(p[i]){
			if(q[i]);
			else ret=(ret*(b-(lower_bound(C,C+b,i+1)-C)))%MOD;
		}else if(q[i])ret=(ret*(a-(lower_bound(R,R+a,i+1)-R)))%MOD;
		else ret=ret*((a-(lower_bound(R,R+a,i+1)-R))*(b-(lower_bound(C,C+b,i+1)-C))-(a*b-i))%MOD;
	}
	printf("%lld\n",ret);
	return 0;
}