SRM 511 DIV1 Medium FiveHundredEleven

SRM DP C++

http://apps.topcoder.com/stat?c=problem_statement&pm=11484&rd=14536

問題

0〜511の数値が書かれたカードが何枚か(1<=N<=50)ある。
値を記録できるメモリがあって、最初は0である。
プレイヤー2人がいて、交互にカードの中から一枚選び、そのカードの数値とメモリの値を bitwise-OR する。そのカードはゲームから取り除かれ、もう使えない。
このとき、そのターンでメモリの値が511になってはいけない。
カードが何も選べなくなった場合そのプレイヤーの負け。
両者が最善をつくすとき、勝つプレイヤーはどちらか？

回答

まず、メモリの値は512通りしか無いのでそのまま状態として持つことが出来るが、カードが使われているかをそのまま持つと2^50となり、それは出来ない。
この時、((mem|card)!=mem)となる場合(もしくは、ビット集合に含まれていない、という意味で(mem&card)!=card)、これは使われてないことがわかることに注意する。
ただ、((mem|card)==mem)となる場合はどうすれば良いか？
そのカードを使ってもメモリの内容は変わらないことに注意すると、そういうカードが複数枚あっても同一視することができる。
また、カードを使った時そのカードは以降の状態で((mem|card)==mem)となるのだから、((mem|card)==mem)となるカードは、それが((mem|card)!=mem)なら少なくとも1つ増え、((mem|card)==mem)だったらそのカード分の1つ減るだけ、ということを考える。
つまり、使ったカードの枚数を状態として数えておき、((mem|card)==mem)である枚数がそれより大きい場合、使われてないカードがあるということだから、ターンを回す事ができる、というふうにできる。

コメント

Editorial見た。
何か戦略があるのかな、とか考えちゃったけど、なるほど、一見独立に見える(見えないかもしれないが)状態を融合し、圧縮できるということか。考え方として重要だ。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#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 aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

bool m[512][52]; bool v[512][52];
struct FiveHundredEleven {
	vi c; int n;
	bool f(int x,int p) {
		if(v[x][p])return m[x][p];
		if(x==511)return true;
		bool r = false;
		int t = 0;
		each(i,c)if((x|*i)==x)++t;
		r|=t>p && !f(x,p+1);
		each(i,c)if((x|*i)!=x){
			r |= !f(x|*i,p+1);
		}
		v[x][p]=1;
		return m[x][p]=r;
	}
	string theWinner(vector <int> cards) {
		c = cards; n = c.size();
		mset(v,0);
		return f(0,0)?"Fox Ciel":"Toastman";
	}
};