Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #102 DIV1 D問題 - Help Shrek and Donkey 2 (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 D問題 (2000pt)
Problem description

問題概要

2人でゲームを行う.validな行動ができなくなった方の負け.
先手必勝か,後手必勝か,永遠にゲームが終わらないかを判定する問題.
n行m列 (100*100以下) のグリッド上に,駒がいくらかある.先手の駒は緑 (G) ,後手の駒は赤 (R).
各行には,駒は2駒以下しかない.
各ターンでは,1駒以上,k駒以下,自分の駒を選んで1マス以上,左右 (同じ行にとどまるよう) に動かす.
ただし,駒を飛び越えたり,盤面の外に出たり,駒をクロスさせるようなことはできない.
また,各ターンの行動は,attackかretreatかを選ばなくてはならなくて,
 attackを選べば,動かす駒は全て,同じ行の敵駒に近づくように動かさなければならなく,
 retreatを選べば,動かす駒は全て,同じ行の敵駒から離れるように動かさなければならない.
同じ行に敵駒がいなければ,その駒はどちらの方向に動かしても良い.

解法

まず,自駒があって,敵駒がいない行があって,しかもそれを1マス以上動かせるなら,そのプレイヤーは負けない.
両方負けないなら,引き分けで,永遠にゲームが終わらない.
勝つ方法は,相手に近づけて,端に追い込んで動けなくすれば良い.
離れることには意味はない(得にならない).離れた分だけ,相手が近づけば同じ状況になるから.
なので,間を近づけることを考えると,n個のNimを考えているのと同じ事になる.
片方だけ,負けない(自由に動かせる駒がある)なら,手番をパスできることに相当するので,必ず勝てる.
Nimのgrundy numberは,石の数,この場合は,自駒と敵駒の間のマスの数.
k個までNimを同時に進行できるので,n個のgrundy numberを2進数表示して,2^iの桁の和 (n個の数字の和) が全てk+1で割り切れるならば,先手の負けとなる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.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;
  int x,y,num;
  int r,g;
  int ok_r, ok_g, ok_v;
  char mp[120][120];
  int grundy[10];

  while(scanf("%d%d%d",&x,&y,&k)==3){
    rep(i,x) scanf("%s",mp[i]);
    ok_g = ok_r = 0;
    rep(i,10) grundy[i] = 0;

    rep(i,x){
      r=g=-1; num = 0;
      rep(j,y){
        if(mp[i][j]=='G') g=j, num++;
        if(mp[i][j]=='R') r=j, num++;
      }
      if(r==-1 || g==-1){
        if(num < y){
          if(g>=0) ok_g = 1;
          if(r>=0) ok_r = 1;
        }
        continue;
      }

      if(r > g) m = r-g-1; else m = g-r-1;
      rep(j,10) if(m&1<<j) grundy[j]++;
    }

    if(ok_g && ok_r){
      puts("Draw"); continue;
    }
    if(ok_g){
      puts("First"); continue;
    }
    if(ok_r){
      puts("Second"); continue;
    }

    rep(i,10) if(grundy[i]%(k+1)) break;
    if(i==10) puts("Second"); else puts("First");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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