けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 694 D1E TryShell

いい問題だった。

問題概要

0 以上 255 以下の整数が n 個与えられる。
この n 個の整数を 3 組に分ける方法のうち、各組の xor 和の総和が最大となるものを求めよ。

(制約)
・3 <= n <= 50

解法

dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k のときの残りの一組の値のとりうる最大値
として解いた。
これなら、以下に示す xor 特有の構造に気づかなくても解ける。

でも、三組の xor 和をそれぞれ a, b, c とし、
n 個全部の整数の xor を sum としたとき、
a ^ b ^ c = sum
なので、
(a ^ b) ^ a ^ b ^ c = (a ^ b) ^ sum
⇔ c = a ^ b ^ sum
なのであった。
このことを利用すればもっと簡明に解ける。

コード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

int dp[2][300][300];

class TrySail {
public:
    int get(vector <int> str) {
        int n = str.size();
        int res = 0;
        for (int i = 0; i < 2; ++i) for (int j = 0; j < 300; ++j) for (int k = 0; k < 300; ++k) dp[i][j][k] = -1;
        dp[0][0][0] = 0;
        for (int i = 0; i < str.size(); ++i) {
            for (int j = 0; j < 256; ++j) for (int k = 0; k < 256; ++k) {
                int cur = dp[i%2][j][k];

                chmax(dp[(i+1)%2][j][k], cur^str[i]);
                chmax(dp[(i+1)%2][j^str[i]][k], cur);
                chmax(dp[(i+1)%2][j][k^str[i]], cur);
            }

            for (int j = 0; j < 256; ++j) for (int k = 0; k < 256; ++k) {
                dp[i%2][j][k] = -1;
            }
        }
        for (int j = 0; j < 300; ++j) for (int k = 0; k < 300; ++k) {
            if (dp[n%2][j][k] != -1) {
                chmax(res, j + k + dp[n%2][j][k]);
            }
        }
        return res;
    }
};