tozangezan's diary

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

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");
	}
}