JOI 2011 予選

この記事はCompetitive Programming Advent Calendar23日目の記事ではありません。

とりあえず適当です
1.狼する

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

2.狼する

#include<stdio.h>
#include<algorithm>
using namespace std;
//NO SPECIFIED SPORTS!!!!
int p[100];
int q[100];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a*(a-1)/2;i++){
		int b,c,d,e;
		scanf("%d%d%d%d",&b,&c,&d,&e);
		b--;
		c--;
		if(d==e){
			p[b]--;
			p[c]--;
		}
		if(d<e){
			p[c]-=3;
		}
		if(e<d){
			p[b]-=3;
		}
	}
	for(int i=0;i<a;i++)q[i]=p[i];
	std::sort(p,p+a);
	for(int i=0;i<a;i++){
		printf("%d\n",lower_bound(p,p+a,q[i])-p+1);
	}
}

3.狼する

#include<stdio.h>
#include<algorithm>
using namespace std;
int dat[100];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<a;i++){
		int e;
		scanf("%d",&e);
		dat[i]=-e;
	}
	std::sort(dat,dat+a);
	int ret=d/b;
	for(int i=0;i<a;i++){
		int sum=0;
		for(int j=0;j<=i;j++)sum-=dat[j];
		ret=max(ret,(sum+d)/(b+(i+1)*c));
	}
	printf("%d\n",ret);
}

4.DPする

#include<stdio.h>
int dp[101][4][2];//day, type, つづきかた
int type[101];
int main(){
	int a,b;
	int MOD=10000;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		type[c]=d;
	}
	dp[0][0][0]=1;
	for(int i=1;i<=a;i++){
		if(type[i]){
			dp[i][type[i]][0]=dp[i-1][0][0];
			if(type[i]==1)dp[i][type[i]][1]+=dp[i-1][1][0];
			else dp[i][type[i]][0]+=dp[i-1][1][1]+dp[i-1][1][0];
			if(type[i]==2)dp[i][type[i]][1]+=dp[i-1][2][0];
			else dp[i][type[i]][0]+=dp[i-1][2][1]+dp[i-1][2][0];
			if(type[i]==3)dp[i][type[i]][1]+=dp[i-1][3][0];
			else dp[i][type[i]][0]+=dp[i-1][3][1]+dp[i-1][3][0];
		}else{
			for(int j=1;j<=3;j++){
				dp[i][j][0]=dp[i-1][0][0];
				for(int k=1;k<=3;k++){
					if(k!=j){
						dp[i][j][0]+=dp[i-1][k][0]+dp[i-1][k][1];
					}else dp[i][j][1]+=dp[i-1][k][0];
				}
			}
		}
		dp[i][1][0]%=MOD;
		dp[i][1][1]%=MOD;
		dp[i][2][0]%=MOD;
		dp[i][2][1]%=MOD;
		dp[i][3][0]%=MOD;
		dp[i][3][1]%=MOD;
	}
	printf("%d\n",(dp[a][1][0]+dp[a][1][1]+dp[a][2][0]+dp[a][2][1]+dp[a][3][0]+dp[a][3][1])%MOD);
}

5.BFSする

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int dat[501][501];
int dx[]={0,0,1,1,-1,-1};
int dy[]={1,-1,-1,0,0,+1};
int bfs[501][501];
int main(){
	int a,b;
	scanf("%d%d",&b,&a);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(j+1+a-(i+1)/2<0)printf("dededon\n");
			scanf("%d",&dat[i+1][j+1+a-(i+1)/2]);
		}
	}
	queue<pair<int,int> > Q;
	Q.push(make_pair(0,0));
	bfs[0][0]=1;
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;
		Q.pop();
		for(int i=0;i<6;i++){
			if(0<=row+dx[i]&&row+dx[i]<=500&&0<=col+dy[i]&&col+dy[i]<=500&&!dat[row+dx[i]][col+dy[i]]&&!bfs[row+dx[i]][col+dy[i]]){
				bfs[row+dx[i]][col+dy[i]]=1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	int ret=0;
	for(int i=1;i<500;i++){
		for(int j=1;j<500;j++){
			for(int k=0;k<6;k++){
				if(dat[i][j]&&bfs[i+dx[k]][j+dy[k]])ret++;
			}
		}
	}
	printf("%d\n",ret);
}

6.DPする(8secくらい? メモリは使いすぎていますが省略可能な気がする)

import java.util.*;
import java.math.*;
class Main{
	static int dp[][][][];
	static int dpA[][][][][];
	static int dpB[][][][][];
	public static void main(String[] args){
		int MOD=10000;
		Scanner s=new Scanner(System.in);
		BigInteger A=s.nextBigInteger();
		BigInteger B=s.nextBigInteger();
		int m=s.nextInt();
		dp=new int[501][m][2][10];//dp[i][j][k][l]:i桁目まででmあまる。最後が↑向きはk=0で↓向きはk=1,最後がl
		dpA=new int[501][m][2][10][2];//最後の1:もう小さいことが確定したのでいくらでも足していいですよ 0:いままでおんなじなんです
		dpB=new int[501][m][2][10][2];
		
		A=A.add(new BigInteger("-1"));
		String a=A.toString();
		String b=B.toString();
		
		for(int i=0;i<501;i++)
			for(int j=0;j<m;j++)
				for(int k=0;k<2;k++)
					for(int l=0;l<10;l++)
						dp[i][j][k][l]=0;
		for(int i=1;i<10;i++){
			dp[0][i%m][0][i]++;
			dp[0][i%m][1][i]++;
		}
		for(int i=0;i<500;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<10;k++){
					dp[i][j][0][k]%=MOD;
					dp[i][j][1][k]%=MOD;
					for(int l=k+1;l<10;l++){
						dp[i+1][(j*10+l)%m][0][l]+=dp[i][j][1][k];
					}
					for(int l=0;l<k;l++){
						dp[i+1][(j*10+l)%m][1][l]+=dp[i][j][0][k];
					}
				}
			}
		}
		
		for(int i=0;i<501;i++)
			for(int j=0;j<m;j++)
				for(int k=0;k<2;k++)
					for(int l=0;l<10;l++)
						dpA[i][j][k][l][1]=dpA[i][j][k][l][0]=0;
		for(int i=1;i<a.charAt(0)-'0';i++){
			dpA[0][i%m][0][i][1]++;
			dpA[0][i%m][1][i][1]++;
		}
		if(a.charAt(0)!='0')dpA[0][(a.charAt(0)-'0')%m][0][(a.charAt(0)-'0')][0]++;
		if(a.charAt(0)!='0')dpA[0][(a.charAt(0)-'0')%m][1][(a.charAt(0)-'0')][0]++;
		for(int i=0;i<a.length()-1;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<10;k++){
					dpA[i][j][0][k][0]%=MOD;
					dpA[i][j][1][k][0]%=MOD;
					dpA[i][j][0][k][1]%=MOD;
					dpA[i][j][1][k][1]%=MOD;
					for(int l=k+1;l<10;l++){
						dpA[i+1][(j*10+l)%m][0][l][1]+=dpA[i][j][1][k][1];
					}
					for(int l=0;l<k;l++){
						dpA[i+1][(j*10+l)%m][1][l][1]+=dpA[i][j][0][k][1];
					}
					for(int l=k+1;l<a.charAt(i+1)-'0';l++){
						dpA[i+1][(j*10+l)%m][0][l][1]+=dpA[i][j][1][k][0];
					}
					for(int l=0;l<Math.min(k,a.charAt(i+1)-'0');l++){
						dpA[i+1][(j*10+l)%m][1][l][1]+=dpA[i][j][0][k][0];
					}
					if(k<a.charAt(i+1)-'0')dpA[i+1][(j*10+a.charAt(i+1)-'0')%m][0][a.charAt(i+1)-'0'][0]+=dpA[i][j][1][k][0];
					if(k>a.charAt(i+1)-'0')dpA[i+1][(j*10+a.charAt(i+1)-'0')%m][1][a.charAt(i+1)-'0'][0]+=dpA[i][j][0][k][0];
				}
			}
		}
		int count=0;
		for(int i=0;i<a.length()-1;i++){
			for(int j=0;j<10;j++){
				count=(count+dp[i][0][0][j])%MOD;
				if(i>0)count=(count+dp[i][0][1][j])%MOD;
			}
		}
		for(int i=0;i<10;i++){
			if(a.length()>1){
				count=(count+dpA[a.length()-1][0][0][i][0]+dpA[a.length()-1][0][0][i][1])%MOD;
			}
			count=(count+dpA[a.length()-1][0][1][i][0]+dpA[a.length()-1][0][1][i][1])%MOD;
		}
	//	System.out.println(count);
		
		for(int i=0;i<501;i++)
			for(int j=0;j<m;j++)
				for(int k=0;k<2;k++)
					for(int l=0;l<10;l++)
						dpB[i][j][k][l][0]=dpB[i][j][k][l][1]=0;
		for(int i=1;i<b.charAt(0)-'0';i++){
			dpB[0][i%m][0][i][1]++;
			dpB[0][i%m][1][i][1]++;
		}
		dpB[0][(b.charAt(0)-'0')%m][0][(b.charAt(0)-'0')][0]++;
		dpB[0][(b.charAt(0)-'0')%m][1][(b.charAt(0)-'0')][0]++;
		for(int i=0;i<b.length()-1;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<10;k++){
					dpB[i][j][0][k][0]%=MOD;
					dpB[i][j][1][k][0]%=MOD;
					dpB[i][j][0][k][1]%=MOD;
					dpB[i][j][1][k][1]%=MOD;
			//		System.out.println(i+" "+j+" "+k+": "+"["+dpB[i][j][0][k][0]+","+dpB[i][j][0][k][1]+","+
			//		dpB[i][j][1][k][0]+","+dpB[i][j][1][k][1]+"]");
					for(int l=k+1;l<10;l++){
						dpB[i+1][(j*10+l)%m][0][l][1]+=dpB[i][j][1][k][1];
					}
					for(int l=0;l<k;l++){
						dpB[i+1][(j*10+l)%m][1][l][1]+=dpB[i][j][0][k][1];
					}
					for(int l=k+1;l<b.charAt(i+1)-'0';l++){
						dpB[i+1][(j*10+l)%m][0][l][1]+=dpB[i][j][1][k][0];
					}
					for(int l=0;l<Math.min(k,b.charAt(i+1)-'0');l++){
						dpB[i+1][(j*10+l)%m][1][l][1]+=dpB[i][j][0][k][0];
					}
					if(k<b.charAt(i+1)-'0')dpB[i+1][(j*10+b.charAt(i+1)-'0')%m][0][b.charAt(i+1)-'0'][0]+=dpB[i][j][1][k][0];
					if(k>b.charAt(i+1)-'0')dpB[i+1][(j*10+b.charAt(i+1)-'0')%m][1][b.charAt(i+1)-'0'][0]+=dpB[i][j][0][k][0];
				}
			}
		}
		int Count=0;
		for(int i=0;i<b.length()-1;i++){
			for(int j=0;j<10;j++){
				Count=(Count+dp[i][0][0][j])%MOD;
				if(i>0)Count=(Count+dp[i][0][1][j])%MOD;
	//			System.out.print(dp[i][0][0][j]+" ");
			}
	//		System.out.println();
		}
		for(int i=0;i<10;i++){
			if(b.length()>1){
				Count=(Count+dpB[b.length()-1][0][0][i][0]+dpB[b.length()-1][0][0][i][1])%MOD;
			}
			Count=(Count+dpB[b.length()-1][0][1][i][0]+dpB[b.length()-1][0][1][i][1])%MOD;
	//		System.out.print(dpB[b.length()-1][0][1][i][0]+dpB[b.length()-1][0][1][i][1]+dpB[b.length()-1][0][0][i][0]+dpB[b.length()-1][0][0][i][1]+" ");
		}
	//	System.out.println(Count);
		Count-=count;
		while(Count<0)Count+=10000;
		System.out.println(Count);
	}
}

1つでもはずした瞬間に命が無くなる競技プログラミング界は怖いですよね。