cafelier@SRM

SRM 540

SRM | 00:07 |

250

• A[0] = x とする
• 例えば B[0] = 100 で op[0]=='+' なら A[1] は 100-x
• 例えば B[1] = 50 で op[0]=='-' なら A[2] は (100-x)-50
• という感じでA[1], ..., A[N-1] を全部 x の一次式で求めてそれが正の数になるという不等式

typedef long long LL;
typedef complex<double> CMP;

class ImportantSequence { public:
   int getCount(vector <int> B, string operators)
   {
      vector< pair<LL,LL> > A;
      A.push_back( make_pair(1,0) ); // A[0] = 1x + 0
      for(int i=0; i<B.size(); ++i)
      {
         LL a = A.back().first;
         LL b = A.back().second;
         LL c = B[i];
         if( operators[i] == '+' ) // (ax+b) + A[i] = c  :: A[i] = -ax + c-b
            A.push_back( make_pair(-a, c-b) );
         else // (ax+b) - A[i] = c   :: A[i] = ax + b-c
            A.push_back( make_pair(a, b-c) );
      }

      static const LL INF = (1LL<<62);
      LL xMin = 1;
      LL xMax = INF;
      for(int i=0; i<A.size(); ++i)
      {
         LL a = A[i].first;
         LL b = A[i].second;
         // ax + b > 0  (aは+1か-1)
         if( a == +1 ) // x > -b
            xMin = max(xMin, -b+1);
         else // -x > -b  == x < b
            xMax = min(xMax, b-1);
      }

      return xMax==INF ? -1 : max(0, int(xMax-xMin)+1);
   }
};

• 問題を見たら探索空間の自由度はどれくらいか？を考える
• どれとどれを決めれば残りが定まるか？と
• 今回の場合一個目 A[0] が決まれば全部決まる
  • 案１： じゃあ可能な A[0] を全通り試そう
  • 案２： 可能な A[0] の上限下限を二分探索とか挟み撃ちとかで賢く探そう
  • 案３： じゃあ A[0] を使って記号的に全部の値を決めよう
• などがあって、現れる演算が + と - しかないことを考えると、「記号的に全部の値を表現」が爆発しないことがわかるのでそれでやってみる、という感じで考えた。

550

• 基本的に問題の定義通りの確率の漸化式をDPで計算するのだけど
• 直方体領域の和は累積和っぽくやって包除原理っぽくやるとO(1)
• コード汚い

class RandomColoring { public:
   double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
   {
      const int dx = d1-1;

      vector< vector< vector<double> > > p(maxR, vector<vector<double> >(maxG, vector<double>(maxB)));
      p[startR][startG][startB] = 1.0;

      for(int i=1; i<N; ++i)
      {
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         for(int b=0; b<maxB; ++b) {
            int c = cnt(maxR, maxG, maxB, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
            - (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
            if( c )
               p[r][g][b] /= c;
            else
               p[r][g][b] = 0;
         }

         vector< vector< vector<double> > > low = p;
         for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         {
            int b = rgb-r-g;
            if( 0<=b && b<maxB ) {
               low[r][g][b] =
                  p[r][g][b]
                  + (r ? low[r-1][g][b] : 0)
                  + (g ? low[r][g-1][b] : 0)
                  + (b ? low[r][g][b-1] : 0)
                  - (r&&g ? low[r-1][g-1][b] : 0)
                  - (g&&b ? low[r][g-1][b-1] : 0)
                  - (b&&r ? low[r-1][g][b-1] : 0)
                  + (r&&g&&b ? low[r-1][g-1][b-1] : 0);
            }
         }

         vector< vector< vector<double> > > q = p;
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         for(int b=0; b<maxB; ++b)
         {
            q[r][g][b] =
                 zone(low, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
               - (d1==0 ? 0 : zone(low, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
         }
         p.swap(q);
      }

      vector< vector< vector<double> > > low = p;
      for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
      for(int r=0; r<maxR; ++r)
      for(int g=0; g<maxG; ++g)
      {
         int b = rgb-r-g;
         if( 0<=b && b<maxB ) {
            low[r][g][b] =
               p[r][g][b]
               + (r ? low[r-1][g][b] : 0)
               + (g ? low[r][g-1][b] : 0)
               + (b ? low[r][g][b-1] : 0)
               - (r&&g ? low[r-1][g-1][b] : 0)
               - (g&&b ? low[r][g-1][b-1] : 0)
               - (b&&r ? low[r-1][g][b-1] : 0)
               + (r&&g&&b ? low[r-1][g-1][b-1] : 0);
         }
      }

      return 1.0 - (
         zone(low, startR-d2, startR+d2, startG-d2, startG+d2, startB-d2, startB+d2)
         - (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx, startG+dx, startB-dx, startB+dx))
      );
   }

   double zone(const vector< vector< vector<double> > >& low,
      int r, int R, int g, int G, int b, int B) {
      r = max(0, min<int>(low.size()-1, r));
      R = max(0, min<int>(low.size()-1, R));
      g = max(0, min<int>(low[0].size()-1, g));
      G = max(0, min<int>(low[0].size()-1, G));
      b = max(0, min<int>(low[0][0].size()-1, b));
      B = max(0, min<int>(low[0][0].size()-1, B));
      return low[R][G][B]
            - (r ? low[r-1][G][B] : 0)
            - (g ? low[R][g-1][B] : 0)
            - (b ? low[R][G][b-1] : 0)
            + (r&&g ? low[r-1][g-1][B] : 0)
            + (g&&b ? low[R][g-1][b-1] : 0)
            + (b&&r ? low[r-1][G][b-1] : 0)
            - (r&&g&&b ? low[r-1][g-1][b-1] : 0);
   }

   int cnt(int maxR, int maxG, int maxB,
      int r, int R, int g, int G, int b, int B) {
      r = max(0, min<int>(maxR-1, r));
      R = max(0, min<int>(maxR-1, R));
      g = max(0, min<int>(maxG-1, g));
      G = max(0, min<int>(maxG-1, G));
      b = max(0, min<int>(maxB-1, b));
      B = max(0, min<int>(maxB-1, B));
      return (R-r+1)*(G-g+1)*(B-b+1);
   }
};