SRM 709 Div1 - ei1333の日記

o– 116.02 points 122th.

1635 -> 1675(+40).

${4}$ 回連続で easy が解けてる.

Easy(250) Xscoregame

TopCoder Statistics - Problem Statement

問題概要

長さ ${n(1 \le n \le 15)}$ の数列 ${A}$ がある.

以下の操作を順に行う.

変数 ${X}$ に ${0}$ をセットする.
数列 ${A}$ の要素 ${Y(0 \le Y \le 50)}$ を左から順に見ていき, ${X}$ を ${X + (X\ xor\ Y)}$ に更新する.

数列 ${A}$ の要素の順番を適切に並び替えたときの最終的な ${X}$ の最大値を求めよ.

解法

制約的にはどうみてもbitdp. どうみてもbitdpなんだけどわからず.（終わり, つらい, 灰色になる）

思考が止まって ${0}$ 完かぁとぼーっとしていると, 突然解法に気づいてあーーってなるいつものアレ.

冷静になって考えてみると, 足される値の変化する箇所は ${X\ xor\ Y}$ . さらに言うと ${Y}$ の値は高々 ${50}$ なので現在の ${X}$ の下位 ${6}$ bit にのみしか影響されない.

dp[bit1][bit2] := 要素の使用済みの状況が bit1 で, そのときの ${X}$ の下位 ${6}$ bit が bit2 のときの ${X}$ の最大値

とすればbitdpができる.

${O(2^{n+\log(\max(Y))} n)}$ .

ソース

#include<bits/stdc++.h>
 
using namespace std;
 
int dp[1 << 15][1 << 6];
const int mask = (1 << 6) - 1;
 
class Xscoregame
{
public:
  int getscore(vector<int> A)
  {
    memset(dp, -1, sizeof(dp));
    
    int N = A.size();
    int ret = 0;
    
    dp[0][0] = 0;
    for(int i = 0; i < (1 << N); i++) {
      for(int j = 0; j < (1 << 6); j++) {
        if(dp[i][j] == -1) continue;
        for(int k = 0; k < N; k++) {
          if((i >> k) & 1) continue;
          int next = (dp[i][j] + (dp[i][j] ^ A[k])) & mask;
          dp[i|(1 << k)][next] = max(dp[i|(1 << k)][next], dp[i][j] + (dp[i][j] ^ A[k]));
          ret = max(ret, dp[i|(1 << k)][next]);
        }
      }
    }
    return(ret);
  }
};