mayoko’s diary

プロコンとかいろいろ。

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;
    }
};