読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

SRM 709 Div1

o– 116.02 points 122th.

1635 -> 1675(+40).

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

Easy(250) Xscoregame

TopCoder Statistics - Problem Statement

問題概要

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

以下の操作を順に行う.

  1. 変数  {X} {0} をセットする.
  2. 数列  {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);
  }
};