cafelier@SRM

SRM500

SRM | 04:41 |

SRM500 の成績・ソース (要ログイン) : AC/TLE/- : 好きな問題セット。汚く書くと酷いことになりバグだらけとなるが整理して書けばバグる余地などなく綺麗になる、というのが顕著に出てくる問題が好きです。

500

class FractalPicture { public:
   double getLength(int x1, int y1, int x2, int y2) 
   {
      return rec(1, x1, y1, x2, y2);
   }

   double rec(int i, int x1, int y1, int x2, int y2)
   {
      x1 = clip<-27,+27>(x1);
      x2 = clip<-27,+27>(x2);
      y1 = clip<  0,+81>(y1);
      y2 = clip<  0,+81>(y2);

      if( i == 501 )
         return 0;
      if( x1<=-27 && 27<=x2 && y1<=0 && 81<=y2 )
         return 81 + (500-i)*54;
      if( x2<=-27 || 27<=x1 || y2<=0 || 81<=y1 )
         return 0;
      double L0 = (x1<=0 && 0<=x2 ? clip<0,54>(y2)-clip<0,54>(y1) : 0);
      x1=x1*3, x2=x2*3, y1=(y1-54)*3, y2=(y2-54)*3;
      double L1 = rec(i+1, x1, y1, x2, y2);
      double L2 = rec(i+1, y1, x1, y2, x2);
      double L3 = rec(i+1, y1, -x2, y2, -x1);
      return L0 + (L1+L2+L3)/3;
   }

   template<int m, int M>
   int clip(int v) { return max(m, min(v, M)); }
};

• 方針としては
  • そのまんま問題の定義通りに、3分岐で再帰して領域に入っている部分の長さを数える
• でよい。
• ただ、本当にそう書くと 3^500 分岐なので終わらないので、
  • 今注目しているnonfinalな線分を種とした図形が
    • 全く (x1,y1)-(x2,y2) の中に入らない == 即座に0を返す
    • 完全にすっぽり (x1,y1)-(x2,y2) の中に入る == 簡単な式で全部の長さが求まるので即座にそれを返す
• とする。
• 「線分の長さは1/3, 1/3, 1/3 になっていくので、すぐにどちらかのパターンに落ちる」ので大した分岐数にはならない

• 問題は、
  • 線分の端点の座標には次々1/3がかかっていくので、それをそのまま持って再帰しているとdoubleが計算に必要になって、
  • ちょっと余計なepsilonなどを入れて入れ方を間違えると、誤差などでどちらのパターンにもうまく落ちずに、もろに3^500再帰することがある。
  • という理由で本番submitしたコードではTLEで死亡
  • （おかしなepsilonの入れ方しなければ大丈夫っぽいですが…）
• 逆に考えて
  • 線分の座標は常に回転、拡大して (0,0)-(0,81) に正規化するようにして、bounding box の方も回転拡大するようにすれば、
  • こっちは3倍3倍なので常に整数座標で処理できる。
  • そうするべき。

250

class MafiaGame { public:
   double probabilityToLose(int N, vector <int> decisions) 
   {
      vector<int> vc;
      {
         map<int,int> voteCnt;
         for(int i=0; i<decisions.size(); ++i)
            voteCnt[decisions[i]] ++;
         for(map<int,int>::iterator it=voteCnt.begin(); it!=voteCnt.end(); ++it)
            vc.push_back( it->second );
      }
      const int MAX = *max_element(vc.begin(), vc.end());
      if( MAX == 1 )
         return 0.0;

      const int GotMAX = count(vc.begin(), vc.end(), MAX);
      for(int k=GotMAX; k!=1; k=(N-k*MAX)%k)
         if( k == 0 )
            return 0.0;
      return 1.0/GotMAX;
   }
};

• 全員1票以下なら下からuniform投票すると全員ピタリ1票になるので無限ループ
• それ以外の場合、鳩ノ巣原理より、下からuniform投票では0票が1票になることしかないので、
• 元々最大得票だった人だけが最終的に最大得票になる。これをGotMAX人とする
  • このGotMAX人は全員対等なので、求める確率は 1/GotMAX しか有り得ない。
  • 無限ループする0.0か、1/GotMAX かどちらかを判定すればよい
  • 固定票MAX票のk人が同率首位のとき、下から投票すうと(N-k*MAX)%k人が頭一つ飛び出すので…
  • というループを繰り返せば判定終わり
• 本番の時は、「元々最大得票だった人だけが最終的に最大得票になる」をコード書くまで気づけなかったのでだいぶ余分なコードを書いてしまった。

SRM500 1000

あとで | 06:48 |

• 意外と、やるだけ問題だった

static const int MODVAL = 500500573; // prime
struct mint
{
   int val;
   mint():val(0){}
   mint(int x):val(x%MODVAL) {}
   mint(LL  x):val(x%MODVAL) {}
};
mint operator+(mint x, mint y) { return x.val+y.val; }
mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
mint POW(mint x, int e) {
   mint v = 1;
   for(;e;x=x*x,e>>=1)
      if(e&1)
         v=v*x;
   return v;
}
mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }

class ProductAndSum { public:
   int getSum(int p2, int p3, int p5, int p7, int S) 
   {
      // Precompute n!, 1/n!, and 111...111
      vector<mint> FACT(2501), FACT_INV(2501), ONES(2501);
      FACT[0] = FACT_INV[0] = 1;
      ONES[0] = 0;
      for(int n=1; n<FACT.size(); ++n)
      {
         FACT[n] = FACT[n-1] * n;
         FACT_INV[n] = 1 / FACT[n];
         ONES[n] = ONES[n-1]*10 + 1;
      }

      mint answer = 0;

      // Exhaustive search over the numbers of 4,6,8,9s : approximately 33*50*50*100/4 ~ 2M iterations
      for(int v8=0; v8*3<=p2; ++v8)
      for(int v4=0; v4*2+v8*3<=p2; ++v4)
      for(int v9=0; v9*2<=p3; ++v9)
      for(int v6=0; v6+v4*2+v8*3<=p2 && v6+v9*2<=p3; ++v6)
      {
         // then, the numbers of 1,2,3s will follow
         int v[] = {-1, -1, p2-v8*3-v4*2-v6, p3-v9*2-v6, v4, p5, v6, p7, v8, v9};
         {
            int v1 = S;
            for(int i=2; i<=9; ++i)
               v1 -= i * v[i];
            if( v1 < 0 )
               continue;
            v[1] = v1;
         }
         int N = accumulate(v+1, v+10, 0);

         // Now, let's compute the sum of all integers, who have N digits and #d = v[d], in constant time!

         // It can be calculated as follows:
         //   Q: how many of the integers have, say "1" in the last digit?
         //   A: it is, of course, C(N-1, v[1]-1, v[2], ..., v[9])
         //      where C(k,a,b,..) is the # of ways of spliting k elements into groups of size a, b, ...
         // So, the sum of the least digits of the integers are
         //   X = \Sigma_{d=1..9} (d * C(N-1, v[1], v[2], ..., v[d]-1, ..., v[9]))
         // By the same argument, the sum of the second-last digits (10-no-kurai in japanese) is
         //   10 * X
         // For hundreds, the sum is 100*X, and so on. Eventualy, the sum of whole integers is
         //   t = (1+10+...+10^N) * X
         //     = 111...111 * \Sigma_{d=1..9} (d * C(N-1, v[1], v[2], ..., v[d]-1, ..., v[9]))
         // Let us simplify the formula by using C(k,a,b,...) = k! / a!b!...
         //   t = 111...111 * \Sigma_{d=1..9} (d * (N-1)! / v[1]! / ... / v[9]! * v[d])
         //     = 111...111 * (N-1)! / v[1]! / ... / v[9]! * \Sigma_{d=1..9} (d*v[d])
         //     = 111...111 * (N-1)! / v[1]! / ... / v[9]! * S
         // That's it!
         mint t = ONES[N] * FACT[N-1] * S;
         for(int i=1; i<=9; ++i)
            t = t * FACT_INV[v[i]];
         answer = answer + t;
      }
      return answer.val;
   }
};

• 1の個数, 2の個数, ..., 9の個数, が決まれば式一発で求まるので、
• その個数として可能なパターンを全部試せばいい。
  • 総和がS, p2, p3, p5, p7 の 5 つの条件式があって
  • 9変数
• なので、4変数の固定のしかたを全通り試せば残りの変数は決まる
• ということで、4,6,8,9の個数が自由度少なめなのでそれを全部動かしてみるとせいぜい2Mパターン。行ける。