TopCoder SRM 694 Div1 Easy TrySail

久々にまともな得点でした。
https://community.topcoder.com/stat?c=problem_statement&pm=14307

問題

N個の整数A[i]が与えられる。
これらを(それぞれ空でない)3つの集合に分ける。
各集合内の整数群のxorを取ったものの和の最大値を求めよ。

解法

P,Q,Rをそれぞれの３つの集合内の整数群の和を取ったものとすると、R=P^Qである。

以下のような状態を考え、A[i]を順に３つの集合に振り分けるケースを考えてDPすればよい。
R=P^QよりRはP,Qから算出できるので、状態として持つ必要はない。
dp[i][x][y][P][Q] := i番目までの整数を3つの集合に振り分けた時、最初2つの集合内の整数群のxorがP,Qとなるものが作れるかどうか。x,yはそれぞれ1・2個目の集合が空かどうかを示す。

最後にdp[N][1][1][P][Q]がTrueであるP,Qに対しP+Q+(P^Q)の最大値を答えればよい。

以下のコードはA[0]は3つめの集合に入れると決め打ちしている。
よって3つめの集合が空であるケースを気にする必要はない。

int from[2][2][256][256];
int to[2][2][256][256];


class TrySail {
	public:
	int get(vector <int> S) {
		int N=S.size();
		int x,y,a,b;
		ZERO(from);
		int sum=S.back();
		S.pop_back();
		from[0][0][0][0]=1;
		
		FORR(r,S) {
			ZERO(to);
			FOR(a,2) FOR(b,2) FOR(x,256) FOR(y,256) if(from[a][b][x][y])
				to[a][b][x][y] = to[1][b][x^r][y] = to[a][1][x][y^r] = 1;
			swap(from,to);
			sum^=r;
		}
		int ma=0;
		FOR(x,256) FOR(y,256) if(from[1][1][x][y]) ma=max(ma,x+y+(sum^x^y));
		return ma;
		
	}
}

まとめ

久々に妙なひっかけの無い普通なEasyが出た気がする…。