beet's soil

競プロのことなど

SRM 709 Div1

よるめ

【250 Xscoregame】

普通にbitDPすると1 2 4 7みたいなケースで落ちる
A_iの範囲が狭いので、下位6bitも持ってDPする。

int getscore(vector <int> A) {
    int n=A.size();
    typedef long long ll;
    static ll dp[1<<16][1<<6];
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<(1<<n);i++){
      for(int k=0;k<(1<<6);k++){
	if(dp[i][k]<0) continue;
	for(int j=0;j<n;j++){
	  if((i>>j)&1) continue;
	  ll nxt=dp[i][k]+(dp[i][k]^A[j]);
	  dp[i+(1<<j)][nxt%64]=max(dp[i+(1<<j)][nxt%64],nxt);
	}
      }
    }
    ll res=0;
    for(int i=0;i<(1<<6);i++)
      res=max(res,dp[(1<<n)-1][i]);
    return (int)res;
  }
【全体】

x-- +1 25points 147th
1446 -> 1498 (+52) highest
初チャレンジ成功?解けなくて全探解と比べてたらコーナーを見つけた。
あと2で黄色!次のeasyがeasyなら勝てる!(フラグ