SRM470 Div1 250 DoorsGame

本番で解けなかった問題シリーズ．

問題

• 部屋0から部屋nが一列に並んでて，部屋はドアで区切られてる
• ドアは高々16種類の色で色分けされている
• Johnが部屋0，Gogoが部屋nにいて，交互にドアを開けながら部屋trophyを目指すゲーム
  • ルール：John先攻で，自分の番では指定した色のドアを全部開ける
  • 先に部屋trophyに到達できる状態になった方が勝ち。同時なら引き分け。
• 互いに最善を尽くしたときの結果を返す問題
  • 勝てる状況なら、最小のターン数で勝つ
  • 負ける状況なら、最大のターン数で負ける
  • 引き分けなら、相手が最小のターン数で来ると仮定してできるだけ引き延ばす

解法

• 本番では16種類に惹かれて謎のビットDPを書いて死亡。
  • ちなみに一行追加したら通って涙目。
• [自分だけに関係ある色]⇒[両者に関係ある色]の順に指定する仮定でシミュレーションするだけ。
  • [相手だけに関係ある色]を開けたとすると
    • 勝てるならターン数が増えるし，それ以外ならターン数が減るので無意味
  • [自分だけに関係ある色]の前に[両者に関係ある色]を開けたとすると
    • 勝てるならターン数が増える可能性がある
    • 負けるならターン数が減ってしまう
    • 引き分けならどうせドアが全部開くので関係ないし、開け方によっては負ける
• 面倒な実装に走る前にこれくらい考えるべき。反省しよう・・・。

#include <iostream>
#include <string>

using namespace std;

class DoorsGame{
private:
    int countBit(int t){
        int cnt;
        for(cnt=0;t;t&=t-1)cnt++;
        return cnt;
    }
public:
    int determineOutcome(string doors, int trophy){
        int A=0, B=0, C=0;
        for(int i=0;i<doors.size();i++){
            if(i<trophy) A |= (1<<(doors[i]-'A'));
            else         B |= (1<<(doors[i]-'A'));
        }
        C = countBit(A&B);
        A = countBit(A)-C;
        B = countBit(B)-C;
        for(int turn=1;;turn++){
            if(turn%2==1){
                if(A>0) A--;
                else if(C>0) C--;
                else B--;
	    } else {
                if(B>0) B--;
                else if(C>0) C--;
                else A--;
            }
            if(A+C==0&&B+C==0) return 0;
            if(A+C==0) return turn;
            if(B+C==0) return -turn;
        }
        return 0;
    }
};