SRM 266 DIV1 Hard AntiChess

問題 Editorial

問題

"Antichess"と呼ばれるゲームをする。
このゲームの目的は自分の駒を全て取られることである。
また、取れる駒があるならそのどれかを必ず取らなければならない。
今、white(自分, 先手)はポーンが何個かだけが残っていて、black(相手, 後手)はクイーンが一つだけ残っている。
ポーンは2のrowに居るときにのみ2つ、その他の場所では1つだけ前に進める。また、ポーンは斜め前に相手の駒がある場合にそこに移動して取ることが出来る(このゲームではそのような状態になった場合に取らないといけない)。
ポーンのrowはどれも2以上で、同じcolumnに2つのポーンが居ることは無い。
ポーンが8のrowに行った場合は成ることは出来ず、そのポーンはもう動けない。全てのポーンが動けなくなった場合は試合はそこで終了である(勝ち負けはこの問題には関係ない)。
"今の状態から連続して"相手に自分の駒を取らせなければいけないような状態にできるターンの長さの最大を求めよ。ただし相手はできるだけそのターンの長さを少なくしようと動く

解答

(ターン * 各columnでポーンがあるかどうか、あるなら位置 * クイーンの位置)で、普通にmapでメモするゲームDP。
自分はポーンの状態をそれぞれ3bit使ってビット列にしてやった。
各ターンでポーンが1つずつ減っていき、クイーンの位置はポーンの位置のどれかになるので状態はそれほど多くはならない

コメント

最初"今の状態から連続して"を"ゲームが終了するまでの"みたいに読み違えてて、クイーンがポーンを取らない動きも考えてたら結構状態多くて枝刈りどうしようかとか考えてた。誤読はやめよう本当に。"sequence"って書いてあるやん

コード

#include <string>
#include <vector>
#include <map>
#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 each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;  

struct AntiChess {
	map<int,int> a[2][8][8];
	int rec(bool turn, int wss, int bc, int br) {
		if(a[turn][bc][br].count(wss)) return a[turn][bc][br][wss];
		int r;
		if(!turn) {
			r = 0;
			rep(i, 8) { int wsi = wss >> i * 3 & 7; if(wsi != 0 && wsi != 8-1) {
				if(wsi+1 == br) {
					if(i-1 == bc) { r = 0; break; }
					else if(i+1 == bc) { r = 0; break; }
					else if(i == bc) continue;
				}
				if(wsi == 2-1 && (wsi+2 != br || i != bc)) {
					r = max(r, rec(true, wss + (1 << i*3+1), bc, br));
				}
				r = max(r, rec(true, wss + (1 << i*3), bc, br));
			} }
		}else {
			r = INF;
			rer(dx, -1, 1) rer(dy, -1, 1) if(dx || dy) {
				int x = bc, y = br;
				while(1) {
					x += dx, y += dy;
					if(y<0||y>=8||x<0||x>=8) break;
					int wsx = wss >> x*3 & 7;
					if(wsx != 0 && wsx == y) {
						r = min(r, 1+rec(false, wss &~ (7 << x*3), x, y));
						break;
					}
				}
			}
			if(r == INF) r = 0;
		}
		return a[turn][bc][br][wss] = r;
	}
	int sacrifice(vector <string> white, string black) {
		vi ws(8, 0);
		each(i, white) ws[(*i)[0]-'a'] = (*i)[1]-'1';
		int wss = 0;
		rep(i, 8) wss |= ws[i] << i * 3;
		int r = rec(false, wss, black[0]-'a', black[1]-'1');
		return r;
	}
};