Top

(ΦωΦ)＜これのつづきですよー。目次はここ。

---
まだまだ頑張る。
2人対戦のこんなゲームをします。
いくつかの部屋が1次元配列状に並んでいて、部屋のそれぞれに猫が高々1匹います。
順番が回ってきた人は、次のどっちかの操作ができます。
A. どっかテキトーな部屋に猫がいるとき、右隣が空き部屋だったら、右隣に猫をずらす。
B. どっかテキトーな部屋に猫がいて、右隣もその右も猫がいて、もうひとつ右は空き部屋だったら、そこ(3つ右)に猫をずらす。
一番右端の部屋の猫は消えます。猫が全部消えたら、消した人が勝ちです。
あなたと相手で交互に操作を繰り返します。あなたは先手です。勝てますか? SRM 534 Div1 Easy or Div2 Med
部屋の数は $20$ 以下。

これも全探索でいいから書けるかい？
ヒント。盤面を2進数だと思って(猫がいる: 1, いない: 0)数字にするといいよ。
猫をずらすというのは、猫を $i$ 番目から取り除いてから別の $j$ 番目に入れる、と考える。
集合 $S$ から $i$ 番目の要素を抜いた集合S & ~(1<<i)

---
まず再帰関数のインターフェースをどうするか。
盤面さえ分かってれば、自分の勝ち負けは決まる。
なので、盤面を整数にしたものを引数にして、勝つのか負けるのかという真偽を返すようにしたい。

再帰関数の内部処理はだいたいどんな感じになるか。
部屋を見て猫がいたら、Aの操作ができるならやってみて、Bの操作ができるならやってみる、こんな感じでいい。

ずらした後の盤面に対し、再帰関数を呼ぶんだけれど、ずらした後の盤面なので相手のターンになる。
なので、この関数の結果が偽だったら自分のターンは真になる。
この考え方は二部グラフ判定の実装(蟻本初版pp.93-94)とかと似ているように思う。

(ΦωΦ)＜全探索
#include <iostream>
#include <algorithm>
using namespace std;

class EllysCheckers { public: string getWinner(string board); };

int n;

bool rec(int mask) {
  bool res = false;
  for(int i=0; i<n; i++) {
    if(!(mask>>i & 1)) { continue; }
    if(i+1 < n && !(mask>>(i+1) & 1)) {
      int nmask = mask & ~(1<<i);
      if(i+1 < n-1) { nmask |= 1<<(i+1); }
      if(!rec(nmask)) { res = true; }
    }
    if(i+3 < n && (mask>>(i+1) & 1) && (mask>>(i+2) & 1) && !(mask>>(i+3) & 1)) {
      int nmask = mask & ~(1<<i);
      if(i+3 < n-1) { nmask |= 1<<(i+3); }
      if(!rec(nmask)) { res = true; }
    } 
  }
  return res;
}

string EllysCheckers::
getWinner(string board) {
  n = board.size();
  int mask = 0;
  for(int i=0; i<n-1; i++) {
    if(board[i] == 'o') {
      mask |= (1 << i);
    }
  }
  return rec(mask) ? "YES" : "NO";
}

---
もうここまで書けたらメモする部分はおまけでしかない。
盤面を全部覚える。
「まだ覚えていない盤面」「答えが真になる盤面」「答えが偽になる盤面」の3つの状態がある。
それぞれにいい感じに数字を振ればいい。
これが素直だと思う。

(ΦωΦ)＜メモ化再帰
#include <iostream>
#include <algorithm>
using namespace std;

class EllysCheckers { public: string getWinner(string board); };

int n;
vector<int> dp;

bool rec(int mask) {
  if(dp[mask] != -1) { return dp[mask]; }
  bool res = false;
  for(int i=0; i<n; i++) {
    if(!(mask>>i & 1)) { continue; }
    if(i+1 < n && !(mask>>(i+1) & 1)) {
      int nmask = mask & ~(1<<i);
      if(i+1 < n-1) { nmask |= 1<<(i+1); }
      if(!rec(nmask)) { res = true; }
    }
    if(i+3 < n && (mask>>(i+1) & 1) && (mask>>(i+2) & 1) && !(mask>>(i+3) & 1)) {
      int nmask = mask & ~(1<<i);
      if(i+3 < n-1) { nmask |= 1<<(i+3); }
      if(!rec(nmask)) { res = true; }
    } 
  }
  return dp[mask] = res;
}

string EllysCheckers::
getWinner(string board) {
  n = board.size();
  dp.assign(1<<n, -1);
  int mask = 0;
  for(int i=0; i<n-1; i++) {
    if(board[i] == 'o') {
      mask |= (1 << i);
    }
  }
  return rec(mask) ? "YES" : "NO";
}

(ΦωΦ)＜forループ
上のメモ化再帰をそのままforループに焼き直そうと思ってもnmaskがmaskより大きくなったり小さくなったりするのでうまくいかなかった…。
#include <iostream>
#include <algorithm>
using namespace std;

class EllysCheckers { public: string getWinner(string board); };

string EllysCheckers::
getWinner(string board) {
  int n = board.size();
  vector<int> dp(1<<n);
  for(int mask=1; mask<1<<n; mask++) {
    if(mask & 1) { continue; }
    dp[mask] = 0;
    for(int i=1; i<n && !dp[mask]; i++) {
      if((mask>>i & 1) && !(mask>>(i-1) & 1)) {
        int nmask = mask & ~(1<<i);
        if(i-1 > 0) { nmask |= 1<<(i-1); }
        if(!dp[nmask]) { dp[mask] = 1; }
      }
    }
    for(int i=3; i<n && !dp[mask]; i++) {
      if((mask>>i & 1) && (mask>>(i-1) & 1) && (mask>>(i-2) & 1) && !(mask>>(i-3) & 1)) {
        int nmask = mask & ~(1<<i);
        if(i-3 > 0) { nmask |= 1<<(i-3); }
        if(!dp[nmask]) { dp[mask] = 1; }
      }
    }
  }
  int m = 0;
  for(int i=0; i<n-1; i++) {
    if(board[i] == 'o') {
      m |= (1 << (n-i-1));
    }
  }
  return dp[m] ? "YES" : "NO";
}

(ΦωΦ)＜つづく