TopCoder SRM 558 Div2 Easy SurroundingGameEasy & Hard CatAndRabbit

ついでにDiv2。今回はHardが900ptとラクだね。
前回のHardは結構苦労したけど。
MediumはDiv1 Easyと同じなので省略。

(URLは掲載待ち)

Easyは指示に従って律儀に計算するだけ。

class SurroundingGameEasy {
	public:
	int st[32][32];
	int ef[32][32];
	int W,H;
	int score(vector <string> cost, vector <string> benefit, vector <string> stone) {
		int x,y,s;
		W=cost[0].size();
		H=cost.size();
		
		ZERO(st);
		FOR(y,32) FOR(x,32) st[y][x]=1;
		FOR(y,H) FOR(x,W) st[y+1][x+1]=(stone[y][x]=='o')?1:0;
		FOR(y,H) FOR(x,W) ef[y+1][x+1]=st[y+1][x+1] | (st[y][x+1] & st[y+1][x] & st[y+2][x+1] & st[y+1][x+2]);
		
		s=0;
		FOR(y,H) FOR(x,W) if(st[y+1][x+1]) s -= cost[y][x]-'0';
		FOR(y,H) FOR(x,W) if(ef[y+1][x+1]) s += benefit[y][x]-'0';
		return s;
		
	}
};

Hardは、まず連続する白マスの数を数えて配列に突っ込む。
全部白マスまたは全部黒マスだと、先手は何もできないので後手のRabbitが勝ち。
それ以外のケースでは、各白マス群は黒マスに接するため白マスがある限り手が打てるので、結局最後の黒マスを埋めれば勝ち。

…これは完全にNimそのまんま。蟻本を見よう。
各全白マス群の数のXORをとり、0じゃなければ先手が勝ち。

class CatAndRabbit {
	public:
	vector<int> nums;
	int N;
	string getWinner(string tiles) {
		int i,c,hb,sc;
		
		nums.clear();
		hb=c=0;
		FOR(i,tiles.size()) {
			if(tiles[i]=='.') c++;
			else {
				if(c>0) nums.push_back(c);
				c=0;
				hb=1;
			}
		}
		if(c>0) nums.push_back(c);
		
		N=nums.size();
		if(hb==0 || N==0) return "Rabbit";
		sc=nums[0];
		for(i=1;i<N;i++) sc^=nums[i];
		if(sc) return "Cat";
		return "Rabbit";
	}
};

まとめ

蟻本にNimが載っていることを知っていたので、Hardがあっさり解けた。
知らないと苦労しそうだな…。