Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-05-06

SRM469 500

| 17:27 | はてなブックマーク -  SRM469 500 - cafelier@SRM

  • 余計な引き算を消しただけ
class TheMoviesLevelTwoDivOne { public:
   vector <int> find(vector <int> length, vector <int> scary) 
   {
      int N = length.size();

      vector<int> lwb(N), inc(N);
      // 寝ないで見終えられる下限
      for(int i=0; i<N; ++i)
         if( scary[i]+47 < length[i] )
            lwb[i] = length[i] - 47;
         else
            lwb[i] = scary[i];
      // 見終わったときの増分
      for(int i=0; i<N; ++i)
         inc[i] = 47 - length[i];

      // メモ化再帰
      memo = vector<bool>(1<<N);
      memo[(1<<N)-1] = true;
      vector<int> temp;
      rec(0, 74, N, lwb, inc, temp);

      // 最適解の後ろに見てない映画を辞書順最小に並べる
      set<int> not_used;
      for(int i=0; i<N; ++i) not_used.insert(i);
      for(int i=0; i<result.size(); ++i)
         not_used.erase(result[i]);
      result.insert(result.end(), not_used.begin(), not_used.end());

      // 以上
      return result;
   }

   vector<int>  result;
   vector<bool> memo;
   void rec(int mask, int cur, int N, vector<int>& lwb, vector<int>& inc, vector<int>& temp)
   {
      if( result.size() < temp.size() )
         result = temp;
      if( memo[mask] )
         return;
      memo[mask] = true;

      for(int i=0; i<N; ++i)
         if( !(mask & (1<<i)) && cur>=lwb[i] )
         {
            temp.push_back(i);
            rec(mask|(1<<i), cur+inc[i], N, lwb, inc, temp);
            temp.pop_back();
         }
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100506
 | 

presented by cafelier/k.inaba under CC0