Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 469 Div1 Medium 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10900&rd=14152:title=SRM 469 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10900&rd=14152:title=SRM 469 Div1 Medium] - shnyaの参戦記録

映画を見た順序を答える問題。全探索は全ての経路を求める場合はO(n!)。

こういう問題は、範囲DP, ソートしてDP, ビットDPのどれかかなぁと思っていて、それぞれ考えてみる。範囲DPに落とせそうな部分的な構造はない。ということで、並び替え頑張ればなんとかならないかなーと思ったけど、無理っぽかった。


結局bitDPに。O(2^20)。最初はvector<signed char>を値にもつメモ化を考えたけど、それだと遅すぎてTLE

配列でやり直したけど、他の人の回答見たら、値を深さでもって、2回再帰すればよかったかなぁとも思ったり。この問題はきつかった。

int setbit(int x, int n){
  return x | 1 << n;
}

int clearbit(int x, int n){
  return x & ~(1 << n);
}

bool testbit(int x, int n){
  return (x & 1 << n) != 0;
}

void printbit(int x){
  for(size_t i = 0; i < sizeof(int) * 8; i++){
    cout << testbit(x,i);
  }
}
typedef signed char uc;
signed char dp[1<<20][21];
signed char depth[1<<20];
int maxn,maxd;

class TheMoviesLevelTwoDivOne {

  void rec(int n, const vector<int> &len, const vector<int> &scary){
    if(n == (1 << len.size()) - 1) return;
    if(depth[n] != -1) return;
    depth[n] = 1;

    int level = 74;
    int cnt = 0;
    for(size_t i = 0; i < len.size(); i++){
      if(testbit(n,i)){
        level += 47;
        level -= len[i];
        cnt++;
      }
    }

    for(size_t i = 0; i < len.size(); i++){
      if(!testbit(n,i)){
        if(level - scary[i] >= 0 && level + 47 - len[i] >= 0){
          int newbit = setbit(n,i);
          if(maxd < cnt + 1){
            maxn = newbit;
            maxd = cnt + 1;
          }
          if(dp[newbit][cnt] == -1){
            for(int j = 0; j < cnt; j++){
              dp[newbit][j] = dp[n][j];
            }
            dp[newbit][cnt] = i;
          }
          rec(newbit, len, scary);
        }
      }
    }
    return;
  }

public:
  vector <int> find( vector <int> length, vector <int> scary ) {
    memset(depth, -1, sizeof(depth));
    memset(dp,-1,sizeof(dp));
    maxn = 0; maxd = 0;
    rec(0, length, scary);
    vector<int> res;
    for(int i = 0; i < maxd; ++i){
      res.push_back(dp[maxn][i]);
    }
    for(int i = 0; i < int(length.size()); i++){
      if(!testbit(maxn,i)){
        res.push_back(i);
      }
    }

    return res;
  }
};