naoya_t@topcoder

SRM370 Div1 Easy: DrawingMarbles

過去問, 練習 | 14:26 |

簡単！と思って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;
  }
};