SRM 694 div1 easy: TrySail
珍しく秒で解ける問題でした(ここまで簡単じゃなくていいけどこういうの 1 つある方が参加する方も楽しくて良いです)。
問題
TopCoder Statistics - Problem Statement
n 人の人がいる。それぞれの人には強さ s[i] が定義されている。n 人を 3 グループに分けるが, それぞれのグループの強さは, そのグループに属する人の s[i] の xor の和で定義される。
グループの強さの和を最大化せよ。
解法
dp[n][s1][s2][flag] = (n 人目までで, 1 グループ目の強さは s1, 2 グループ目の強さは s2 となっていることはあり得るか)という dp を考えます。flag はすでに i グループ目に人がいたら (flag > > i)&1 が 1 です。
各 i について, s[i] を s1, s2, s3 のどれに入れるかを考えます。
s3 は考えなくて良いのかと思われるかもしれませんが, s1^s2^s3 = (s[0] ^ s[1] ^ ... ^ s[n-1]) ( = sum とする) となるので, s3 = sum ^ s1 ^ s2 で求められるので, 最大値を求めるときは, dp[n][s1][s2][flag] が true のものについて調べれば s3 の情報も抽出できます。
bool dp[55][256][256][8]; class TrySail { public: int get(vector <int> s) { int n = s.size(); memset(dp, 0, sizeof(dp)); dp[0][0][0][0] = true; for (int i = 0; i < n; i++) for (int j = 0; j < 256; j++) for (int k = 0; k < 256; k++) for (int flag = 0; flag < 8; flag++) { if (!dp[i][j][k][flag]) continue; dp[i+1][j^s[i]][k][flag|1] = 1; dp[i+1][j][k^s[i]][flag|2] = 1; dp[i+1][j][k][flag|4] = 1; } int sum = 0; for (int i = 0; i < n; i++) sum ^= s[i]; int ans = 0; for (int i = 0; i < 256; i++) for (int j = 0; j < 256; j++) { if (!dp[n][i][j][7]) continue; ans = max(ans, i+j+(sum^i^j)); } return ans; } };