AOJ1151～1160 - c21coterie @ ウィキ

aoj1156 Twirling Robot

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156

動的計画法で解ける簡単な問題。
普通に解くと少し遅いので優先順位付きキューとメモ化を使って気持ち高速化して解く。
平均的な速度とメモリ使用量で解けた。
方向転換の命令を使った場合使わなかった場合で後はキューが勝手にコスト順でソートしながら幅優先探索するだけ。

#include<stdio.h>
#include<queue>
struct point{
int x,y,a,cost;
bool operator<(const point& p)const{
	return cost>p.cost;
}
};
bool calc(){
int map[31][31];
int arrowChange[5][4]={	{0,1,2,3},
			{3,0,1,2},
			{2,3,0,1},
			{1,2,3,0},
			{4,4,4,4}};
int dxs[5]={1,0,-1,0,0};
int dys[5]={0,-1,0,1,0};
int colSize,rowSize;
int memo[31][31][5];
int mymax=1000000;	
scanf("%d %d",&colSize,&rowSize);
if(rowSize==0&&colSize==0)return false;
for(int r=0;r<rowSize;r++){
	for(int c=0;c<colSize;c++){
		scanf("%d",&map[r][c]);
		for(int k=0;k<5;k++)memo[r][c][k]=mymax;
	}
}
int costs[4];
for(int i=0;i<4;i++)scanf("%d",&costs[i]);
memo[0][0][0]=0;
std::priority_queue<point> points;
point p,nextP;
p.x=p.y=p.a=p.cost=0;
points.push(p);
while(points.empty()==false){
	p=points.top();
	//printf("\n(%d %d %d)",p.x,p.y,p.cost);
	if(p.y==rowSize-1&&p.x==colSize-1){
		printf("%d\n",p.cost);
		break;
	}		
	points.pop();
	for(int i=0;i<4;i++){
		//iは方向転換の命令
		int nextCost=p.cost;
		if(map[p.y][p.x]!=i){
			nextCost+=costs[i];
		}
		int nextArrow=arrowChange[i][p.a];
		nextP.y=p.y+dys[nextArrow];
		nextP.x=p.x+dxs[nextArrow];
		nextP.a=nextArrow;
		nextP.cost=nextCost;
		//printf("<%d %d %d>",nextP.x,nextP.y,nextP.cost);
		if(nextP.x<0||nextP.x>=colSize||nextP.y<0||nextP.y>=rowSize)continue;
		if(nextP.cost>=memo[nextP.y][nextP.x][nextP.a])continue;
		memo[nextP.y][nextP.x][nextP.a]=nextP.cost;
		points.push(nextP);
	}
}
return true;
}
int main(){
while(calc()){
}
}

1159　Next Mayor

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1159
ちょっとした小石取りゲームをシミュレートする問題。
数式を使うのが一番賢いのだろうけど、そんな方法を思いつきそうもなかったので問題で指定されたルール通り愚直に実装。
賢い方法？なにそれ。

#include<stdio.h>
#include<string.h>
void calc(int n,int p){
int memo[51],count,p1=0,max=p;
memset(memo,0,sizeof(memo));
while(1){
	if(p==0){
		p=memo[p1];
		memo[p1]=0;
	}else{
		memo[p1]++;
		p--;
	}
	if(memo[p1]==max)break;
	p1=(p1+1)%n;
}
printf("%d\n",p1);
}
int main(){
int n,p;
while(1){
	scanf("%d %d",&n,&p);
	if(n==0&&p==0)break;
	calc(n,p);
}
}