Pの競プロ記

競技プログラミングに関することを書きます。

FiveHundredEleven (SRM511 div2 hard)

解法・感想など


Editorial見ました。

こういうゲーム理論の問題は自力ではまだ解けないですね、勉強しないと。
(ズラズラと書いていくので、日本語おかしいところがあるかもしれません。)

このゲームでの勝敗条件は以下の通りです。
・自分の番で引くカードがなければ負け
・自分の番でカードを引いてメモリの計算をした時、その値が511になれば負け
(メモリの値が511の状態で自分の番になれば勝ち)

こういう問題はメモ化再帰で解きます。

dp[ 現在のメモリの値 ][ 何回カードを引いたか ] = その状態から最善を尽くした時の勝敗
(勝ち = 1、負け = 0、まだ定まっていない = -1)

このようにメモリの値とカードを引いた回数の2つが分かれば、全状態をメモ化しておくことができます。

なぜでしょうか?
それはメモリの値に影響しないカードは全て一緒であると考えることができ、以下のような処理をすることで使ったカードと使ってないカードを分けることができるからです。

メモリの値の計算は、カードに書いてある値とメモリの値のorを取ります。
ですから以下のような処理をすると、「すでに使ったカード、またはメモリの値に影響しないカード」と「まだ使っていないカード」に分けることができます。

int cnt = 0;    
for(int i = 0; i < cards.size(); i++) {
  if((memory | cards[i]) == memory) cnt++;
}

再帰させるとき、現在のメモリの値とカードを引いた回数を持たせるので
「cnt - カードを引いた回数 = まだ使っていないメモリの値に影響しないカード」を求めることができます。

それにより、自分の番でメモリに影響を与える動作をするかどうかを選ぶことができるようになります。

あとはメモ化させながら解くことができます。

ゲームの勝敗を決める問題で大切な考え方


今回の問題を通じて、学んだことをちょっとメモしておきます。

再帰させるとき、「勝ち」が返ってきたときは「負け」、「負け」が返ってきた時は「勝ち」という考え方。
以下の処理では

if(!isWinning((memory | cards[i]), played + 1)) win |= true;

再帰させたときの返り値が偽であれば真を取っています。
つまり「相手が負ければ自分は勝ち」、「相手が勝てば自分は負け」となります。
文章で書くと当然のことですが、この考え方を再帰で表現するのはきちんと覚えてないいけませんね。

○(上のコードの「win |= true;」のように)、orを取るという考え方。
「お互いが最善を尽くしたときの勝敗を決める」
この「お互いが最善を尽くしたとき」って文章が今までよく分かりませんでした。
これも以下の処理では、このように現在の状態からいろんな状態に遷移し、1つでも偽が返ってくれば真となります。

if(!isWinning((memory | cards[i]), played + 1)) win |= true;

つまりいろんな状態に遷移しても全て真が返ってくるとき、偽となり自分は負けとなります。 全て真が返ってくるとは、現在の状態がどのような手を打っても負けてしまう、つまり最善を尽くしても負けてしまうということになります。

だいぶ日本語がおかしくなってると思いますが、最善を尽くすというのはこういうことだと(私は)解釈しました。


ソースコード

class FiveHundredEleven {
public:
  vector<int> cards;
  int dp[512][51];
  
  int isWinning(int memory, int played) {
    if(memory == 511) return 1; // win
    if(played == cards.size()) return 0; // lose
    if(dp[memory][played] != -1) return dp[memory][played];

    int cnt = 0;
    bool win = false;
    for(int i = 0; i < cards.size(); i++) {
      if((memory | cards[i]) == memory) cnt++;
    }
    
    if(cnt > played) {
      if(!isWinning(memory, played + 1)) win |= true;
    }
    
    for(int i = 0; i < cards.size(); i++) {
      if((memory | cards[i]) != memory) {
        if(!isWinning((memory | cards[i]), played + 1)) win |= true;
      }
    }

    return dp[memory][played] = win;
  }

  string theWinner(vector <int> c) {
    cards = c;
    memset(dp, -1, sizeof(dp));

    return isWinning(0, 0) ? "Fox Ciel" : "Toastman";
  }
};