naoya_t@topcoder

SRM460

04:06 |

02.06+.2010

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

DIV	level	問題名	競技中	後で	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) これは落ちて当然

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