長期の大会に初めて参加しました！(高校の時に参加したSuperconを別にすれば、ですが) 初体験で、どうかなと思っていたのですが、これからはTopcoderのmarathonも含めて、参加してみていいなと思いました。とはいえ、忙しい時期もよくあるので、参加できる範囲で、ということにします。
今回私は "Infinite Grid Game"という問題を解きました。そこで、このアルゴリズムを説明しようと思います。
簡単のため、ゴールを(0,0)とします。平行移動すれば同値であることがわかるはずです。
さて、もしもコマが(n,0),(0,n),(n,n) (nは自然数です)のどれかにあれば、次に動かすプレイヤーが勝つことがわかります。
ですので、これらの負ける点には動かすべきではありません。しかし、(1,2)や(2,1)にあった場合、 これらの負ける点に動かさねばなりません。つまり、(1,2)または(2,1)に動かしたほうが勝ちです。ということは、(1,3),(1,4),...と、負ける点が判明します。
これを繰り返していくと、勝ち負けの地図ができますので、これを作ればOKです。
例えばボブが勝つのは:(1,2),(2,1),(3,5),(5,3) ...であり、他の点ならアリスに軍配が上がります。
地図を作って出力する、というプロセスで、簡単に問題をとくことができますね。
コンテスト内での順位は116位でした。
ロングコンテストでのRatingがnon-ratedから2.787になり1785位となりました。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NUM 1000
int main(void){
int m,n,i,j,k,x,y;
int t,p,q;
short board[NUM][NUM];
memset(board,0,sizeof(board));
for(i=0;i<=2000;i++){
for(j=0;j<=i;j++){
if(j>=1000) break;
if(abs(i-j)>=1000) continue;
if(board[j][abs(i-j)]!=0) continue;
for(x=j+1;x<1000;x++) board[x][abs(i-j)]=1;
for(y=abs(i-j)+1;y<1000;y++) board[j][y]=1;
for(k=1;j+k<1000 && abs(i-j)+k<1000;k++) board[j+k][abs(i-j)+k]=1;
}
}
scanf("%d",&t);
while(t--){
scanf("%d %d %d %d",&m,&n,&p,&q);
if(board[m-p][n-q]==0) puts("Bob");
else puts("Alice");
}
return 0;
}
0 件のコメント:
コメントを投稿