この記事は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つでもはずした瞬間に命が無くなる競技プログラミング界は怖いですよね。
