Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1638-2c65dfe6
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #36 D問題 - New Game with a Chess Piece (この記事を編集する[管理者用])

Source

Codeforces Beta Round #36 D問題
Problem description
Beta Round #36の自分の参加記録
SPOJ 7602 [CF36D] (2010-10-21 01:25追加)

問題概要

n*mのチェス盤の左上にコマがある.
2人でゲームを行う.順番にコマを動かしていき,行える行動がなくなったら負け.
出来る行動は,右に1マス動かすか,下に1マス動かすか,右下ななめにkマスだけ動かす.
先手必勝か後手必勝か判定する問題.
n,m,kは1以上10億以下.

解法

小さい時に全探索すると規則が見える.
ただし,k=1のときのみ例外的な形をしている.
規則が見えると,それが先手必勝になることの証明はできなくもないはず.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,q;
  int a,b;

  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  scanf("%d%d",&q,&k);
  while(q--){
    scanf("%d%d",&a,&b); a--; b--;
    if(k==1){
      if(a%2==1||b%2==1) puts("+"); else puts("-");
      continue;
    }
    if(a>b) m=a, a=b, b=m;
    b-=a;
    a %= 2*(k+1);
    if(a==k || a==2*k+1){puts("+"); continue;}
    if(a<=k) b++;
    if(b%2) puts("-"); else puts("+");
  }

  return 0;
}
規則を見つけるためのコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int k;
int dp[50][50];

int solve(int a,int b){
  int i,j,res=0;
  
  if(dp[a][b] >=0) return dp[a][b];

  if(a && solve(a-1,b)==0) res=1;
  if(b && solve(a,b-1)==0) res=1;
  if(a>=k && b>=k && solve(a-k,b-k)==0) res=1;

  return dp[a][b]=res;
}

int main(){
  int i,j,l,m,n;

  k=3;
  rep(i,50) rep(j,50) dp[i][j]=-1;
  rep(i,50){
    rep(j,50){
      if(j<i){putchar(' '); continue;}
      if(solve(i,j)) putchar('o');
      else putchar('x');
    }
    puts("");
  }

  return 0;
}
規則を見つけるためのコードの出力結果
xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
 xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
  xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
   ooooooooooooooooooooooooooooooooooooooooooooooo
    oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
     oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
      oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
       ooooooooooooooooooooooooooooooooooooooooooo
        xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
         xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
          xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
           ooooooooooooooooooooooooooooooooooooooo
            oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
             oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
              oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
               ooooooooooooooooooooooooooooooooooo
                xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
                 xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
                  xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
                   ooooooooooooooooooooooooooooooo
                    oxoxoxoxoxoxoxoxoxoxoxoxoxoxox
                     oxoxoxoxoxoxoxoxoxoxoxoxoxoxo
                      oxoxoxoxoxoxoxoxoxoxoxoxoxox
                       ooooooooooooooooooooooooooo
                        xoxoxoxoxoxoxoxoxoxoxoxoxo
                         xoxoxoxoxoxoxoxoxoxoxoxox
                          xoxoxoxoxoxoxoxoxoxoxoxo
                           ooooooooooooooooooooooo
                            oxoxoxoxoxoxoxoxoxoxox
                             oxoxoxoxoxoxoxoxoxoxo
                              oxoxoxoxoxoxoxoxoxox
                               ooooooooooooooooooo
                                xoxoxoxoxoxoxoxoxo
                                 xoxoxoxoxoxoxoxox
                                  xoxoxoxoxoxoxoxo
                                   ooooooooooooooo
                                    oxoxoxoxoxoxox
                                     oxoxoxoxoxoxo
                                      oxoxoxoxoxox
                                       ooooooooooo
                                        xoxoxoxoxo
                                         xoxoxoxox
                                          xoxoxoxo
                                           ooooooo
                                            oxoxox
                                             oxoxo
                                              oxox
                                               ooo
                                                xo
                                                 x

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1638-2c65dfe6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。