Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM522 DIV1 EASY - RowAndCoins / DIV2 MEDIUM - RowAndManyCoins (この記事を編集する[管理者用])

Source

TopCoder SRM522 DIV1 EASY (250pt)
TopCoder SRM522 DIV2 MEDIUM (550pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

長さn以下のAかBからなる文字列が与えられる.
2人でゲームを行う.順番に行動する.
各ターン,まだ消されていない連続する文字の区間を1つ選び,その区間の文字を消す.(消された両隣の文字の間は空白となり,ひっつかない)
全ての文字が消えるような選択はできない.
一文字だけ残ったときにゲームは終了し,残った文字がAなら先手の勝ち,Bなら後手の勝ち.
先手必勝かどうかを判定する問題.
DIV1はnは14以下,DIV2はnは50以下.

解法

ちょっとした考察で,両端が両方共Aの時のみ先手必勝であることがわかる.
理由は,連続する文字の区間の数を数えた時,自分の区間を1つ増やすか,敵の区間をn+1個消し自分をn個消すか,ぐらいの行動にしか意味が無い.
DIV1はビットマスクを使った探索でも良い.以下のコードはDIV1用で探索している.

C++によるスパゲッティなソースコード (DIV1用)
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int n;
string cell;
int dp[2][500000];
int go[1000], go_size;

int solve(int play, int mask){
  int i,j,k;
  int rest; char rest_c;
  int res = 0;

  if(dp[play][mask] >= 0) return dp[play][mask];

  rest = 0;
  rep(i,n) if(!(mask & 1<<i)){
    rest++;
    rest_c = cell[i];
  }

  if(rest==1){
    if(play==0 && rest_c=='A') res = 1;
    if(play==1 && rest_c=='B') res = 1;
    return dp[play][mask] = res;
  }

  rep(i,go_size){
    k = go[i];
    if( mask & k ) continue;
    if( (mask | k) == (1<<n)-1 ) continue;

    if(solve(play^1, mask|k)==0){ res = 1; break; }
  }

  return dp[play][mask] = res;
}

class RowAndCoins {
public:
string getWinner(string cells) {
  int i,j,k;
  string res;

  cell = cells;
  n = cell.size();

  go_size = 0;
  rep(i,n) REP(j,i,n){
    go[go_size] = 0;
    REP(k,i,j+1) go[go_size] |= (1<<k);
    go_size++;
  }

  rep(i,2) rep(j,500000) dp[i][j] = -1;

  k = solve(0,0);
  if(k) return "Alice";
  return "Bob";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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