SRM 244 DIV1 Hard ConnectFour

問題 Editorial

問題

6*7の盤面での"Connect Four"の局面が与えられる。
その局面に到達することが可能かかどうか、もし到達可能なら次はどのプレイヤーか、もしくはどのプレイヤーが既に勝っているか、あるいはもう打つ手はない(引き分け)か、を返せ

解答

空中に浮いてる局面は問答無用でinvalidとすると、与えられた局面までの局面は7^7の、それぞれの列の高さの配列として表される。
それでDPすればその局面に到達可能かどうかは判定できる。
どちらかが勝っている時は、直前まで勝っていない状態でなければならないことに注意してやる

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi; typedef vector<string> vs;

const int pow7[8] = {1,7,49,343,2401,16807,117649,823543};
int dp[2][823543];
const string invalid = "invalid";
const string moves[2] = {"second player moves", "first player moves"};
const string wins[2] = {"first player wins", "second player wins"};
const string draw = "draw game";
const string xo = "XO";
struct ConnectFour {
	static const int H = 6, W = 7;
	vs b;
	int rec(bool turn, int hs) {
		if(dp[turn][hs] != -1) return dp[turn][hs];
		int r = 0;
		if(hs == 0) {
			r = turn == true;
		}else {
			int x = hs;
			rep(j, W) {
				if(x % 7 != 0 && b[H - x % 7][j] == xo[turn]) {
					r |= rec(!turn, hs - pow7[j]);
				}
				x /= 7;
			}
		}
		return dp[turn][hs] = r;
	}
	bool isWon(bool t, int x) {
		vi hs; rep(j, W) hs.pb(x % 7), x /= 7;
		bool r = false;
		#define OK(y, x) (0 <= x && x < W && 0 <= y && y < H && H - (y) <= hs[x] && b[y][x] == xo[t])
		rep(j, W) rep(i, H) {
			 r |= OK(i+0, j) && OK(i+1, j) && OK(i+2, j) && OK(i+3, j);
			 r |= OK(i, j+0) && OK(i, j+1) && OK(i, j+2) && OK(i, j+3);
			 r |= OK(i+0, j+0) && OK(i+1, j+1) && OK(i+2, j+2) && OK(i+3, j+3);
			 r |= OK(i-0, j+0) && OK(i-1, j+1) && OK(i-2, j+2) && OK(i-3, j+3);
		}
		return r;
	}
	string judge(vector <string> board) {
		b = board;
		int hs = 0;
		rep(j, W) {
			rer(i, 0, H) if(i == H || b[i][j] != '.') {
				reu(k, i, H) if(b[k][j] == '.') return invalid;
				hs += pow7[j] * (H - i);
				break;
			}
		}
		mset(dp, -1);
		int a = 0, c = 0;
		rep(t, 2) {
			a |= rec(t, hs) << t;
			c |= isWon(t, hs) << t;
		}
		if(a == 0) return invalid;
		if(c == 0) {
			if(hs == pow7[7]-1) return draw;
			else return moves[a - 1];
		}
		if(a - 1 != c - 1) return invalid;
		if(c == 3) return invalid;
		bool d = false;
		rep(j, W) if(hs / pow7[j] % 7 != 0 && b[H - hs / pow7[j] % 7][j] == xo[c - 1]) {
			d |= !isWon(c - 1, hs - pow7[j]) && rec(!(c - 1), hs - pow7[j]);
		}
		if(d) return wins[c - 1];
		return invalid;
	}
};