Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #3 C問題 - Tic-tac-toe (この記事を編集する[管理者用])

Source

Codeforces Beta Round #3 C問題
Problem description
Beta Round #3の自分の参加記録

問題概要

Tic-tac-toe (3×3の升目に○か×を書いて3目並べするあれ)の盤面が与えられる.
それが,
 絶対にありえない盤面
 次のターンが先手
 次のターンが後手
 ちょうど先手が勝ったところ
 ちょうど後手が勝ったところ
 ちょうど引き分けになったところ
のどれかを判定する問題.

解法

解法は主に2通り.

1つ目は,場合分けして求める方法.
×のマークの数と,○のマークの数を数えて,後攻のほうが多かったり,先攻の方が2個以上多かったりするとありえなくて,そうでなければどっちの番かはわかる.
後は,最後に打った人じゃない人が既に勝っているなども不正.
この方針は,全ての場合のパターンをすぐにもれなく考えられるなら実装も早いし,計算量も小さい.

2つ目は,実際にシミュレーションして,盤面を全部作成してしまう方法.
状態数は高々3^9しかないので,計算時間は問題ない.
変なコーナーケースなどを考えなくて良いので,ミスは少ないと思う.
以下のソースコードはこっちの方針.

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 pw[12];
int check[20000];

void doit(int mask,int turn){
  int i,j,k,mp[9],win=0;

  if(check[mask]>=0) return;

  k=mask;
  rep(i,9) mp[i]=k%3, k/=3;

  rep(i,3){
    if(mp[i*3+0] && mp[i*3+0]==mp[i*3+1] && mp[i*3+1]==mp[i*3+2]) win=mp[i*3+0];
    if(mp[i  +0] && mp[i  +0]==mp[i  +3] && mp[i  +3]==mp[i  +6]) win=mp[i  +0];
  }
  if(mp[0] && mp[0]==mp[4] && mp[4]==mp[8]) win=mp[0];
  if(mp[2] && mp[2]==mp[4] && mp[4]==mp[6]) win=mp[2];

  if(win){ check[mask]=1+win; return; }
  rep(i,9) if(!mp[i]) break;
  if(i==9){ check[mask]=4; return; }

  check[mask]=turn;
  rep(i,9) if(mp[i]==0) doit(mask+pw[i]*(turn+1),turn^1);
}

int main(){
  int i,j,k,l,m,n;
  char mp[99];

  pw[0]=1; REP(i,1,12) pw[i]=pw[i-1]*3;
  rep(i,pw[9]) check[i]=-1;

  doit(0,0);
  rep(i,3) scanf("%s",mp+i*3);
  k=0;
  rep(i,9){
    k*=3;
    if(mp[8-i]=='X') k++;
    if(mp[8-i]=='0') k+=2;
  }

  if(check[k]==-1) puts("illegal");
  if(check[k]== 0) puts("first");
  if(check[k]== 1) puts("second");
  if(check[k]== 2) puts("the first player won");
  if(check[k]== 3) puts("the second player won");
  if(check[k]== 4) puts("draw");
  
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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