Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2010-05-06

SRM469 1000

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

  • だいたいあってた
class TheMoviesLevelThreeDivOne { public:
   long long find(vector <int> timeJ, vector <int> timeB) 
   {
      int N = timeJ.size();
      return (1LL<<N) - quitJ(N, timeJ, timeB) - quitJ(N, timeB, timeJ);
   }

   LL quitJ(int N, vector<int>& J, vector<int>& B) // # of patterns in which J quits
   {
      typedef pair<int,int>            state;
      typedef map<state, LL>::iterator iter;

      map<pair<int,int>, LL> M;
      M[state(0,-0x3fffffff)] = 1;

      for(int i=0; i<N; ++i)
      {
         map<state, LL> M2;
         for(iter it=M.begin(); it!=M.end(); ++it)
         {
            int sum   = it->first.first;
            int bound = it->first.second;
            LL  n     = it->second;

            M2[state(sum+J[i],      bound-J[i])]           += n; // i goes to J
            M2[state(sum+J[i]-B[i], max(bound, B[i]-sum))] += n; // i goes to B
         }
         M2.swap(M);
      }

      LL cnt = 0;
      for(iter it=M.begin(); it!=M.end(); ++it)
         if( 0 < it->first.second )
            cnt += it->second;
      return cnt;
   }
};
  • Σ J[...] と Σ (J-B)[...] を別々に覚える必要はない
  • 足しちゃってよい。

  • あらためて整頓する。
    • Σ_{0≦i<N} f(i) < timeB[x]
    • where
      • f(i) = timeJ[i] if "i-th movie goes to J"
      • f(i) = timeJ[i]-timeB[i] if "i<x" and "i-th movie goes to B"
  • となる x が存在すると、J が B に追いついてしまう。
  • このパターン数を全部数える。

  • 上のソースコードで
    • sum がだいたい Σ_{0≦i<x} f(i)
    • bound が timeB[x] - Σ_{0≦i<N} f(i) の最大値
    • n が sum と bound がそうなるパターン数
  • 最終的に bound > 0 なパターン数が答え
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100506
 | 

presented by cafelier/k.inaba under CC0