Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-14

SRM370 Div1 Easy: DrawingMarbles

| 14:26 | SRM370 Div1 Easy: DrawingMarbles - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM370 Div1 Easy: DrawingMarbles - naoya_t@topcoder SRM370 Div1 Easy: DrawingMarbles - naoya_t@topcoder のブックマークコメント

簡単!と思ってsubmitした(241.68pt)がFailed System Test→再挑戦(10%減点。201.60pt)

  • 分母の2500C50とかlong longじゃ無理でしょでしょ
  • c()をdoubleにすればOK。long doubleにするほどのことではない模様

失敗作:

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

long long c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}

class DrawingMarbles {
 public:
  double sameColor(vector<int> colors, int n) {
    int cn=sz(colors);
    long long num=0LL;
    int total=0LL;
    rep(i,cn){
      int ci=colors[i]; total+=ci;
      if(ci>=n) num+=c(ci,n);
    }
    return 1.0 * num / c(total,n);
  }
};

成功作:

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

double c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1.0;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}

class DrawingMarbles {
 public:
  double sameColor(vector<int> colors, int n) {
    int cn=sz(colors);
    double r=0.0;
    int total=0LL;
    tr(colors,it) total+=(*it);
    double denom=c(total,n);
    rep(i,cn){
      int ci=colors[i]; total+=ci;
      if(ci>=n) r+=c(ci,n)/denom;
    }
    return r;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090114