久々にまともな得点でした。
https://community.topcoder.com/stat?c=problem_statement&pm=14307
問題
N個の整数A[i]が与えられる。
これらを(それぞれ空でない)3つの集合に分ける。
各集合内の整数群のxorを取ったものの和の最大値を求めよ。
解法
P,Q,Rをそれぞれの3つの集合内の整数群の和を取ったものとすると、R=P^Qである。
以下のような状態を考え、A[i]を順に3つの集合に振り分けるケースを考えて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が出た気がする…。