「AOJ1151～1160」の編集履歴（バックアップ）一覧はこちら
「AOJ1151～1160」(2012/07/18 (水) 18:16:24) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*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()){
}
}
*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);
}
}
