Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM470 DIV1 EASY (250pt)
TopCoder SRM470 DIV2 MEDIUM (500pt)
Problem Statement
SRM 470 自分の参加記録

問題概要

2人でゲームをする.
一列に連なった部屋の間に鍵のかかったドアがある.
最初,それぞれのプレイヤーは両端にいて,ある部屋を目指す.
鍵は16種類以下で,順番にどの種類の鍵を解除するかを指定していく.指定された鍵のドアは全部開く.
勝てるなら最小ターンで,負けるなら最大ターンで負けるようにする.
勝敗とターン数を求める問題.

解法

解放は幾つかある.
1つ目は,ビットDP.実装は重たいけど確実.
2つ目は,greedy.基本的に自分しか開けないといけない鍵があればそれを開ける.
その後は,勝てるなら,残りの鍵を開けていく.勝てないなら,無駄な鍵を開けていく.
3つ目は,自分しか開けないといけない鍵の数,療法が開けないといけない鍵の数から,解析的に求める.
ちょっと考えると,意外と単純に求まることに気づく.
以下のコードはビットDP.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

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

#define INF 1000000000

int A, B;
int dp[1200000];

void ne(int *now,int *old){
  if(*now < 0 && *old < 0){
    if(*now < *old) *now=*old;
  }
  if(*now >= 0 && *old <= 0) *now=*old;
  if(*now > 0 && *old > 0){
    if(*now < *old) *now = *old;
  }
}

int solve(int mask,int step){
  int i,j,k;
  int a, b;
  int m1, m2;
  int res, tmp, t;

  if(dp[mask]!=INF) return dp[mask];

  res=1;
  rep(i,16) if(!(mask&1<<i)){
    m1 = (mask|(1<<i));
    
    a=b=0;
    if(A==(m1&A)) a=1;
    if(B==(m1&B)) b=1;

    if(a && b) tmp = 0;
    else if(a) tmp = -(step+1);
    else if(b) tmp = (step+1);
    else{
      tmp = 1;
      rep(j,16) if(!(m1&1<<j)){
        m2 = (m1|(1<<j));

        a=b=0;
        if(A==(m2&A)) a=1;
        if(B==(m2&B)) b=1;
        if(a && b) t=0;
        else if(a) t = (step+2);
        else if(b) t = -(step+2);
        else       t = -solve(m2,step+2);

        ne(&tmp,&t);
      }
      tmp *= -1;
    }

    ne(&res,&tmp);
  }

  return dp[mask]=res;
}

class DoorsGame {
public:
int determineOutcome(string doors, int trophy) {
  int i,j,k;
  int res;

  A=B=0;
  rep(i,doors.size()){
    k=doors[i]-'A';
    if(i<trophy) A|=(1<<k);
    else         B|=(1<<k);
  }
  
  rep(i,1<<16) dp[i]=INF;
  res = solve(0,0);

  return -res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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