naoya_t@topcoder

SRM460 Easy: TheQuestionsAndAnswersDivOne

過去問 | 17:10 |

全パターン試すのそんなに難しくないし…

まあ目が覚めてて落ち着いてれば解ける問題でした。

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

int fact(int x)
{
  int val = 1;
  for (int i=x; i>1; i--) val *= i;
  return val;
}

class TheQuestionsAndAnswersDivOne {
  int qn,an;
  vector<int> ans,pat;

  bool match() {
    vector<int> d(qn,-1); //毎回allocateするのどうよ
    rep(i,an){
      int q = pat[i], a = ans[i];
      if (d[q]<0) d[q]=a;
      else if (d[q]!=a) return false;
    }
    return true;
  }
  int test(int qi,int ai) {
    int cnt=0;
    if (qi==qn) {
      if (ai<an) return 0;
      // vector<int> t(all(pat));
      do {
        if (match()) cnt++;
      } while(next_permutation(all(pat)));
      return cnt;
    } else {
      int qr = qn - qi;
      int ar = an - ai, rest = ar - qr;
      for (int c=1;c<=1+rest;c++) {
        for (int i=ai;i<ai+c;i++) pat[i]=qi;
        cnt += test(qi+1,ai+c);
      }
      return cnt;
    }
  }
 public:
  int find(int questions, vector <string> answers) {
    qn=questions, an=sz(answers);
    if (qn==an) return fact(qn);
    ans.resize(an); rep(i,an) ans[i]=(answers[i]=="Yes")?1:0;
    pat.assign(an,-1);
    return test(0,0);
  }
};

• passed system test

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点台に安定している。駄目だこりゃ