cafelier@SRM

SRM469 1000

あとで | 17:50 |

• だいたいあってた

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 なパターン数が答え