問題
http://community.topcoder.com/stat?c=problem_statement&pm=10915&rd=14153
AからPまでの16色のいずれかの色がついたドアがある。
Johnは最初左端におり、Brusは最初右端にいる。
Johnからスタートし、交互に好きな色を選んでいく。
選ばれた色のドアはすべてオープンする。
また、トロフィーが置かれている場所もわかっている。
このとき、Johnが勝つときはそのターン数を、
Brusが勝つときはそのターン数にー１をかけたものを、
引き分けのときは０を返す。
解き方
色の選び方は最大１６！となり単純な全探索では解くことができない。
今回、JohnとBrusがドアを開けていくのに必要な情報は、
「john側だけにある色数」「Brus側だけにある色数」「両方にある色のドアの色数」
だけであり、各ドアの色の種類や数は関係ない。
上記の集合に変換することができれば、
あとは各プレイヤーが最適な戦略をとるようにして全探索で解くことができる。
コード
class DoorsGame {
public: int determineOutcome(string doors, int trophy) {
int n=doors.size();
int a=0,b=0,common=0;
for(char ch='A';ch<='P';ch++){
int flaga=0,flagb=0;
for(int j=0;j<trophy;j++)if(doors[j]==ch)flaga=1;
for(int j=n-1;j>=trophy;j--)if(doors[j]==ch)flagb=1;
if(flaga && flagb)common++;
else if(flaga)a++;
else if(flagb)b++;
}
int turn=0;
while(a+b+common>0){
turn++;
if(turn%2){
if(a>0)a--;
else if(common>0)common--;
else b--;
}
else{
if(b>0)b--;
else if(common>0)common--;
else a--;
}
if(a+b+common==0)return 0;
else if(a+common==0)return turn;
else if(b+common==0)return -turn;
}
return -1;
}
};
public: int determineOutcome(string doors, int trophy) {
int n=doors.size();
int a=0,b=0,common=0;
for(char ch='A';ch<='P';ch++){
int flaga=0,flagb=0;
for(int j=0;j<trophy;j++)if(doors[j]==ch)flaga=1;
for(int j=n-1;j>=trophy;j--)if(doors[j]==ch)flagb=1;
if(flaga && flagb)common++;
else if(flaga)a++;
else if(flagb)b++;
}
int turn=0;
while(a+b+common>0){
turn++;
if(turn%2){
if(a>0)a--;
else if(common>0)common--;
else b--;
}
else{
if(b>0)b--;
else if(common>0)common--;
else a--;
}
if(a+b+common==0)return 0;
else if(a+common==0)return turn;
else if(b+common==0)return -turn;
}
return -1;
}
};