naoya_t@topcoder

SRM466 Medium: LotteryPyaterochka

過去問 | 22:24 |

• いきなりN=100とか考えてたから混乱した
• 500Ｃ5 = 255244687600 はlong longに収まる
• N=1,N=2,N=3,と順に落ち着いて全パターンを洗い出す。{5},{4,1},{3,2},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1}の合計が1になることをデバッグの為に確認して、{5},{4,1},{3,2},{3,1,1} までの和を返せば計算がちゃんと合った。

typedef long long ll;

ll c(int n, int r) // nCr
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}
ll fac(int x) // x!
{
  ll val = 1;
  for (ll i=x; i>1; i--) val *= i;
  return val;
}

class LotteryPyaterochka {
public:
  double chanceToWin(int N) {
// BEGIN CUT HERE
    //if (N<=2) return 1.0; // まあこれでいいんですが以下の数え上げのデバッグの為にコメントアウト
// END CUT HERE

    ll all = c(N*5,5);// c(5,5)=1 .. c(500,5)=255244687600
    
    ll p = 0;
    // 5
    p += c(N,1) * fac(1) * 1;
    if (N>=2) {
      // 41
      p += c(N,2) * fac(2) * c(5,4) * c(5,1);
      // 32
      p += c(N,2) * fac(2) * c(5,3) * c(5,2);

      if (N>=3) {
        // 311
        p += c(N,3) * 3 * c(5,3) * c(5,1) * c(5,1);
// BEGIN CUT HERE
        /* 以下、数え上げのデバッグの為
        // 221
        p += c(N,3) * 3 * c(5,2) * c(5,2) * c(5,1);
        if (N>=4) {
          // 2111
          p += c(N,4) * 4 * c(5,2) * c(5,1) * c(5,1) * c(5,1);
          if (N>=5) {
            // 11111
            p += c(N,5) * 1 * c(5,1) * c(5,1) * c(5,1) * c(5,1) * c(5,1);
          }
        }
        */
// END CUT HERE
      }
    }
// BEGIN CUT HERE
    //printf("%lld / %lld\n", p, all);
// END CUT HERE
    return (double)p / all;
  }
};

• passed system test