WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM694 Div1 Easy "TrySail"

解法

dpる。
まず全員をteam1に加入させておく。
それから、生徒ごとに着目していき、team2及びteam3に移籍させる場合を考えていく。
team2及びteam3それぞれのチーム力とすることが可能かどうか記録しておき、それを更新していく。

dp[team2/team3それぞれのチーム力] := それが可能?

事後

255は0x11111111じゃない。。0b11111111だったよ。。orz

ソースコード

bool dp[2][1 << 16];

class TrySail {
    public:
    int get(vector<int> strength) {
        int n = strength.size();

        // 全員チーム1に加入しとく
        int all = 0;
        for (int i = 0; i < n; i++) {
            all ^= strength[i];
        }

        // dp初期化
        for (int i = 0; i < 2; i++) {
            for (int b = 0; b < (1 << 16); b++) {
                dp[i][b] = false;
            }
        }
        int cur = 0;
        int next = 1;
        dp[cur][0] = true;

        // dp更新
        for (int i = 0; i < n; i++) {
            // next初期化
            for (int b = 0; b < (1 << 16); b++) {
                dp[next][b] = false;
            }
            // 加入していく
            for (int b = 0; b < (1 << 16); b++) {
                if (!dp[cur][b]) continue;
                // チーム1に残留
                dp[next][b] = true;
                // チーム2に移籍
                dp[next][b ^ strength[i]] = true;
                // チーム3に移籍
                dp[next][b ^ (strength[i] << 8)] = true;
            }
            // cur next交代
            cur = 1 - cur;
            next = 1 - next;
        }

        // 答え算出
        int answer = 0;
        for (int b = 0; b < (1 << 16); b++) {
            if (!dp[cur][b]) continue;
            int t2 = b & 0b11111111;
            int t3 = (b >> 8) & 0b11111111;
            int t1 = all ^ t2 ^ t3;
            answer = max(answer, t1 + t2 + t3);
        }
        return answer;
    }
};