Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-02-07

SRM460

04:06 | SRM460 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM460 - naoya_t@topcoder SRM460 - naoya_t@topcoder のブックマークコメント

02.06+.2010

エントリしてうたた寝して起きたら2:11amとか

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 TheQuestionsAndAnswersDivOne submitted - x - failed system test
1 500 TheFansAndMeetingsDivOne 間に合わず - - -
1 1000 - 開いてない -

Easy: TheQuestionsAndAnswersDivOne

  • 計算あわなくて時間かかった
  • しかしサンプルケースが通るだけの計算式・・・
  • 以下、駄目コード
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

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;
}
int fact(int x)
{
  int val = 1;
  for (int i=x; i>1; i--) val *= i;
  return val;
}
int pw(int x,int y){
  int val=1;
  rep(j,y) val*=x;
  return val;
}

class TheQuestionsAndAnswersDivOne {
 public:
  int find(int questions, vector <string> answers) {
    int z=sz(answers),y=0,n=0;
    rep(i,z) if(answers[i]=="Yes") y++; n=z-y;

    int t=0;
    set<pair<int,int> > pt;
    rep(p,1<<questions){ //4,512
      int cy=__builtin_popcount(p),cn=questions-cy;
      if(cy>y || cn>n) continue;
      if(cy==0 && y>0) continue; if (cn==0 && n>0) continue;
      pt.insert(make_pair(cy,cn));
    }
    tr(pt,it) {
      int cy=it->first, cn=it->second;
      int dy=y-cy, dn=n-cn;
      int a=C(y,cy)*pw(cy,dy);
      int b=C(n,cn)*pw(cn,dn);

      t+=a*b*C(questions,cn);
        
    }
    return t;
  }
};

Medium: TheFansAndMeetingsDivOne

  • 残りの15分ぐらいで考えた
  • 途中まで考えた・・・

Hard: 開いてない

Challenge Phase

  • なぜか撃墜されず。部屋に赤だれもいないからかね

System Test

  • 落とされ

x - -

0点

Practice Room

{4,{"Yes", "No", "Yes", "No", "Yes", "Yes", "Yes", "No"}}とかで落ちてる。しょぼすぎる。

結果

room:12/12位

DIV1:427/698位

1392→1337(-55) これは落ちて当然

http://gyazo.com/5c2ac1e392c74270db3764775bc31992.png

見事に1300点台に安定している。駄目だこりゃ

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100207