House of Cards (UVa Live Archive World Finals Stockholm 2009)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2452

問題

2*M枚のカードをルールに従って山を作るように互いに置いていく。どちらが勝ち、スコアの差分がどうなるか求めよ。
5<=M<=13

解法

αβ法を用いて探索するだけ。状態の持ち方を工夫すればそんなにひどいことにはならないがバグを入れてしまうと結構厄介なんで注意して書くこと。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
int base[5][5];
int peak[4][10];
int cards[100];
char name[100];

inline int Score(int c, int card) {
  int s = 1;
  if (c != card / 100) { s = -1; }
  return card % 100 * s;
}

inline int Score3(int c, int card1, int card2, int card3) {
  int num[2] = { 0, 0 };
  num[card1 / 100]++;
  num[card2 / 100]++;
  num[card3 / 100]++;
  int s = 1;
  if (num[c] < num[c ^ 1]) { s = -1; }
  return (card1 % 100 + card2 % 100 + card3 % 100) * s;
}

#define UPDATE_ALPHA() \
  ret = max(ret, nret); \
  alpha = max(ret, alpha); \
  if (alpha >= beta) { return ret; }

int calc(int depth, int c, int score, int pHand, int eHand, int alpha, int beta) {
  if (depth == n * 2) {
    return score + Score(c, pHand) - Score(c ^ 1, eHand);
  }
  int ret = -1000000000;
  int nHand = cards[depth];
  if (pHand == 0) {
    int nret = -calc(depth + 1, c ^ 1, -score, eHand, nHand, -beta, -alpha);
    UPDATE_ALPHA();
  }
  REP(iter, 2) {
    REP(y, 4) {
      REP(x, y + 1) {
        if (pHand != 0 && base[y][x] == 0 && peak[y][2 * x + 1] != 0 && peak[y][2 * x + 2] != 0) { 
          base[y][x] = pHand;
          int nscore = score + Score3(c, pHand, peak[y][2 * x + 1], peak[y][2 * x + 2]);
          int nret = -calc(depth + 1, c ^ 1, -nscore, eHand, nHand, -beta, -alpha);
          base[y][x] = 0;
          UPDATE_ALPHA();
        }
        if (pHand != 0 && nHand != 0 && base[y + 1][x] != 0 && peak[y][2 * x] == 0 && peak[y][2 * x + 1] == 0) {
          peak[y][2 * x] = pHand;
          peak[y][2 * x + 1] = nHand;
          int nscore = score + Score3(c, base[y + 1][x], pHand, nHand);
          int nret = -calc(depth + 1, c ^ 1, -nscore, eHand, 0, -beta, -alpha);
          peak[y][2 * x] = 0;
          peak[y][2 * x + 1] = 0;
          UPDATE_ALPHA();
        }
      }
    }
    swap(pHand, nHand);
  }
  //cout << depth << " " << c << " " << score << " " << ret << endl;
  return ret;
}

int main() {
  int test_case = 0;
  while (scanf("%s", name), name[0] != 'E') {
    test_case++;
    MEMSET(base, 0);
    MEMSET(peak, 0);
    scanf("%d", &n);
    REP(i, 2 * n) {
      int v;
      char c;
      scanf("%d %c ", &v, &c);
      cards[i] = v + 100 * (c == 'B' ? 0 : 1);
      if (i < 8) { peak[3][i] = cards[i]; }
    }
    int turn = cards[0] / 100;
    int ans = calc(8, turn, 0, 0, 0, -10000000, 10000000);
    int want = name[0] == 'B' ? 0 : 1;
    printf("Case %d: ", test_case);
    if (ans == 0) {
      printf("Axel and Birgit tie\n");
    } else if ((want == turn && ans > 0) ||
        (want != turn && ans < 0)) {
      printf("%s wins %d\n", name, abs(ans));
    } else {
      printf("%s loses %d\n", name, abs(ans));
    }
  }
}