SRM 709 Div1 easy : Xscoregame

問題概要 :

長さ n (1 <= n <= 15) の数列 A が与えられる
Aの各要素A[i]は 0 以上 50 以下である
この数列に対して以下の処理を行う

1. 変数 X を用意し、 X に 0 を代入する
2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する :
X = X + ( X xor A[i] )
　 これを選べる要素がなくなるまで続ける
3. X の値を出力する

最終的に X のとりうる最大の値を答えよ

解法 :
ビットDP
dp[Aのどの要素を使ったかをbitで保持, 1<<15][下位6bit x, 1<<6] = 下位6bit が x であるような値の最大値

愚直にやると、bool dp[state1][state2]
bool dp[Aのどの要素を使ったかをbitで保持, 1<<15][ Aの要素を使用した状態が state1 であるときの最大値 ] = state2を作れるか
とやれば良い
ただ、サンプルの最後を見るとわかる通りstate2がかなり大きくなる

Xの値を計算する際に xor をとるため、単純に大きい値だけを保持していてもそれが最終的に最大値になるかどうかはわからない
そのためbitの情報をすべて state2 としてとっていたのだが、A[i] <= 50 であることに注目すればわざわざ全てのbitの情報を保持しておく必要がないことが分かる
なぜなら、( X xor A[i] ) において X の 6bit目以降は xor の計算で影響を受けない
なので6bit目以下だけをdpの状態として保持すれば良い

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

#define MAX 64

int dp[1<<15][MAX];

class Xscoregame {
public:
  int getscore(vector <int> A) {
    int n = A.size();
    sort(A.begin(),A.end());    
    memset(dp,-1,sizeof dp);
    dp[0][0] = 0;
    rep(bit,(1<<n)) {
      rep(bet,MAX) {
	if( dp[bit][bet] == -1 ) continue;
	rep(i,n) {
	  if( (bit>>i) & 1 ) continue;
	  int nbit = bit | (1<<i);
	  int value = dp[bit][bet] + ( dp[bit][bet] ^ A[i] );
	  int beet = value % MAX;
	  dp[nbit][beet] = max(dp[nbit][beet],value);
	}
      }
    }
    int maxi = 0;
    rep(i,MAX) maxi = max(maxi,dp[(1<<n)-1][i]);
    return maxi;
  }
};