AOJ 2200,2441,2153
とりあえず難易度表の500を埋めていくことにする。
2200:
適宜最短路を求めたらDPするだけ。どこに500要素があるのかわからない。数が中途半端に大きく迷惑。
#include<stdio.h> #include<algorithm> using namespace std; int dp[1001][200]; int L[200][200]; int S[200][200]; char str[2]; int z[1000]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ for(int i=0;i<a;i++) for(int j=0;j<a;j++) L[i][j]=S[i][j]=111111111; for(int i=0;i<a;i++)L[i][i]=S[i][i]=0; for(int i=0;i<b;i++){ int c,d,e; scanf("%d%d%d%s",&c,&d,&e,str); c--;d--; if(str[0]=='S')S[c][d]=S[d][c]=min(S[c][d],e); else L[c][d]=L[d][c]=min(L[c][d],e); } for(int k=0;k<a;k++) for(int i=0;i<a;i++) for(int j=0;j<a;j++){ L[i][j]=min(L[i][j],L[i][k]+L[k][j]); S[i][j]=min(S[i][j],S[i][k]+S[k][j]); } int r; scanf("%d",&r); for(int i=0;i<r;i++) for(int j=0;j<a;j++) dp[i][j]=2111111111; for(int i=0;i<r;i++){scanf("%d",z+i);z[i]--;} dp[0][z[0]]=0; for(int i=0;i<r-1;i++){ for(int j=0;j<a;j++){ if(dp[i][j]>=2111111111)continue; if(L[z[i]][z[i+1]]<111111111)dp[i+1][j]=min(dp[i+1][j],dp[i][j]+L[z[i]][z[i+1]]); for(int k=0;k<a;k++){ if(L[z[i]][j]<111111111&&S[j][k]<111111111&&L[k][z[i+1]]<111111111)dp[i+1][k]=min(dp[i+1][k],dp[i][j]+L[z[i]][j]+S[j][k]+L[k][z[i+1]]); } } } int ret=2111111111; for(int i=0;i<a;i++)ret=min(ret,dp[r-1][i]); printf("%d\n",ret); } }
2441:
二分探索してFizzBuzzの表記に使う文字数を求めると楽。実はあっさり書ける問題。
import java.util.*; class Main{ static long calc(long a){ long ret=a/3*4+a/5*4; int l=0; for(long p=1;a>=p;p*=10){ l++; long R=Math.min(a,p*10); long L=p-1; ret+=((R-R/3-R/5+R/15)-(L-L/3-L/5+L/15))*l; } return ret; } public static void main(String args[]){ Scanner s=new Scanner(System.in); long a=s.nextLong(); long left=0L; long right=200000000000000000L; while(left+1<right){ long M=(left+right)/2; if(calc(M)>=a)right=M; else left=M; } String str=""; long M=left; for(int i=1;i<20;i++){ if((M+i)%15==0)str+="FizzBuzz"; else if((M+i)%3==0)str+="Fizz"; else if((M+i)%5==0)str+="Buzz"; else str+=""+(M+i); } int ss=(int)(a-calc(M)-1); String ret=""; for(int i=0;i<20;i++)ret+=str.charAt(i+ss); System.out.println(ret); } }
2153:
BFS。添字のxとyを間違えた
#include<stdio.h> #include<queue> #include<algorithm> using namespace std; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; char L[50][51]; char R[50][51]; struct wolf{ int ax,ay,bx,by; }; int bfs[50][50][50][50]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ for(int i=0;i<b;i++){ scanf("%s%s",L[i],R[i]); } for(int i=0;i<b;i++) for(int j=0;j<a;j++) for(int k=0;k<b;k++) for(int l=0;l<a;l++) bfs[i][j][k][l]=0; queue<wolf>Q; wolf S; for(int i=0;i<b;i++) for(int j=0;j<a;j++){ if(L[i][j]=='L'){ S.ax=i; S.ay=j; } if(R[i][j]=='R'){ S.bx=i; S.by=j; } } bfs[S.ax][S.ay][S.bx][S.by]=1; Q.push(S); while(Q.size()){ wolf at=Q.front(); Q.pop(); for(int i=0;i<4;i++){ wolf to=at; to.ax+=dx[i]; to.ay+=dy[i]; to.bx+=dx[i]; to.by-=dy[i]; //printf("%d %d %d %d\n",to.ax,to.ay,to.bx,to.by); bool okL=true; bool okR=true; if(0>to.ax||b<=to.ax)okL=false; if(0>to.bx||b<=to.bx)okR=false; if(0>to.ay||a<=to.ay)okL=false; if(0>to.by||a<=to.by)okR=false; if(okL&&L[to.ax][to.ay]=='#')okL=false; if(okR&&R[to.bx][to.by]=='#')okR=false; if(!okL){ to.ax-=dx[i]; to.ay-=dy[i]; } if(!okR){ to.bx-=dx[i]; to.by+=dy[i]; } //printf("%d %d %d %d\n\n",to.ax,to.ay,to.bx,to.by); if(!bfs[to.ax][to.ay][to.bx][to.by]&&((L[to.ax][to.ay]=='%'&&R[to.bx][to.by]=='%')||(L[to.ax][to.ay]!='%'&&R[to.bx][to.by]!='%'))){ bfs[to.ax][to.ay][to.bx][to.by]=1; Q.push(to); } } } wolf G; for(int i=0;i<b;i++) for(int j=0;j<a;j++){ if(L[i][j]=='%'){ G.ax=i; G.ay=j; } if(R[i][j]=='%'){ G.bx=i; G.by=j; } } if(bfs[G.ax][G.ay][G.bx][G.by])printf("Yes\n"); else printf("No\n"); } }