cafelier@SRM

SRM501

SRM | 22:19 |

SRM501 の成績・ソース (要ログイン) : WA/AC/-: 許される限りの限界の計算量で答えを探そう

500

template<typename T>
struct DP4
{
   int N1, N2, N3, N4;
   vector<T> data;
   DP4(int N1, int N2, int N3, int N4, const T& t = T())
      : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
   T& operator()(int i1, int i2, int i3, int i4)
      { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
};

static const int MODVAL = 1000000007;

class FoxAverageSequence { public:
   int theCount(vector <int> seq) 
   {
      const int N = seq.size();

      DP4<LL> dp(N,2,41,40*N+1);
      for(int b=0; b<=40; ++b)
         if( seq[0]==-1 || seq[0]==b )
            dp(0,0,b,b) += 1;

      for(int i=1; i<N; ++i)
         for(int dn=0; dn<=1; ++dn)
         for(int  b=0;  b<=40; ++b)
         for(int  s=0;  s<=40*i; ++s)
         if( LL v = dp(i-1,dn,b,s) )
            for(int c=0; c<=min(40,s/i); ++c)
               if( seq[i]==-1 || seq[i]==c )
                  if( !dn || b<=c )
                     (dp(i,b>c,c,s+c) += v) %= MODVAL;

      LL ans = 0;
      for(int dn=0; dn<=1; ++dn)
      for(int  b=0;  b<=40; ++b)
      for(int  s=0;  s<=40*N; ++s)
         ans += dp(N-1,dn,b,s);
      return ans % MODVAL;
   }
};

• dp(i,dn,b,s) =
  • seq[i] までを埋めたときに
  • seq[i-1]＞seq[i] (dn==1のとき) または seq[i-1]≦seq[i] (dn==0のとき) であって、
  • seq[i] に b が入っていて
  • 和が seq[0] + ... + seq[i] = s
• な埋め方は何通りあるか。
• という表を左から順に埋めていく。
• 40*2*40*1600*40 (最後の40は表を進める最内周ループの分) ≒ 2億
• よりは適度に小さい感じなので、まあこのくらいなら、まず書いてみて間に合わなかったらその時考えればよいと思う。
• 実際は0.7sくらいだったので余裕

250

class FoxPlayingGame { public:
   double theMax(int nA, int nB, int paramA, int paramB) 
   {
      const double scoreA = paramA / 1000.0;
      const double scoreB = paramB / 1000.0;

      double cur=scoreA*nA, best=cur;
      for(int i=0; i<=nB; ++i, cur*=scoreB)
         best = max(best, cur);
      return best;
   }
};

• どのタイミングで何個 B を使うかを変化させると
  • (scoreA*scoreB^i[1] + scoreA*scoreB^i[2] + ... + scoreA*scoreB^inA)
    • ただし i[1] ～ i[nA] は 0以上nB以下の任意の値
• が全部作れることがすぐわかる。
• 各項ごと最大化すればいいので、i[1]～i[nA] を違う値にする意味はないので
  • (scoreA * nA * scoreB^i) where 0≦i≦nB
• を最大化すればよくて、あとは全部試す。

• 実際には等比数列は2個おきに見れば単調性があるから i=0,1,nB-1,nB だけ試せば十分
• なんだけど、計算量が許すなら全部試してmaxとる方が安全確実なのでそうするべき

• 本番は i=0,nB-1,nB だけ試すコードで死亡