cafelier@SRM

SRM428 Div1 1000 (2008/12/12)

あとで | 14:28 |

埋め込んでない埋め込んでないよ！（ということにしておく）

O(n * 3^n) の NegaMax を無理矢理押し通した。最悪ケース "XXXXXXXXXXXXXXXX" で 1.85s。

これが想定解と言うことはないと思うので解説待ち…

#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

char memo[81*81*81*81];
int  n, X[16];
static const char NIL = 99;

bool win[243];

class TheStringGame
{
public:
  string winner(string s) 
  {
    // construct the winning condition table
    for(int mm=0; mm<243; ++mm)
      win[mm] = (mm/9%3==0 &&
          (  mm/81%3==2 && mm/27%3==1     // LOX
          || mm/27%3==2 && mm/ 3%3==2     //  LXL
          || mm/ 3%3==1 && mm/ 1%3==2 )); //   XOL

    // read the input
    int m=0, numX=0;
    {
      memset(memo, NIL, sizeof(memo));
      n = s.size();
      for(int i=0; i<n; ++i) {
        m *= 3;
        for(int j=0; j<numX; ++j)
          X[j] *= 3;
  
        if( s[i]=='X' )
          X[numX++] = 1;
        else
          m += (s[i]=='O' ? 1 : 2);
      }
    }

    // solve
    if( int r = negaMax(m, numX) )
    {
      stringstream sout;
      sout << (r>0 ? "John" : "Brus") << " " << numX-abs(r)+1;
      return sout.str();
    }
    return "Draw";
  }

  static int rev(int m)
  {
    int z = 0;
    for(int i=0; i<n; ++i)
      z = z*3 + m%3, m/=3;
    return z;
  }

  static char negaMax(int m, int numX)
  {
    if( numX == 0 )
      return 0;
    if( memo[m] != NIL )
      return memo[m];

    for(int j=0; j<numX; ++j)
      if( win[m*9/X[j]%243] )
        return memo[m] = numX;

    int sc = -numX;
    for(int j=0; j<numX; ++j) {
      int M = X[j];
      swap(X[j], X[numX-1]);
      sc = max(sc, -negaMax(m+M*1, numX-1));
      sc = max(sc, -negaMax(m+M*2, numX-1));
      swap(X[j], X[numX-1]);
    }
    return memo[m] = memo[rev(m)] = sc;
  }
};