Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-02-18

SRM462

13:34 | SRM462 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM462 - naoya_t@topcoder SRM462 - naoya_t@topcoder のブックマークコメント

wataさんと同じ部屋

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 AgeEncoding o(再提出) - passed - 85.34
1 450 CandyBox o - passed - 235.35
1 1000 WarTransportation 未提出 -

Easy(250): AgeEncoding

  • ばいなりさーち
  • 上限下限の算定が間違ってて範囲内に見つからないぞ
  • 直す
  • n進法で再計算するところも間違ってて計算ずれてる
  • 直す
  • submitted(33'20'')
  • Mediumの問題を開く
  • が、戻ってきて適当なテストケースを2,3追加
  • "111"では1歳は表現できんだろ
  • でも"110"で1歳は行けるんだよな
  • 仕方ない。再提出するか
  • 85.34pts (penalty 10% included)
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#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++)

class AgeEncoding {
  vector<int> v; int k; double g;
  double rt(int a,int n){
    return pow((double)a, 1.0/n); }
  double q(double z){
    double x=1.0, a=0;
    rep(i,k){
      a += x * v[i];
      x *= z;
    }
    return a;
  }
  double md(double lo,double hi) {
    double m=(lo+hi)/2;
    if(hi-lo < 1e-9) return m;
    return q(m)>g ? md(lo,m) : md(m,hi);
  }
 public:
  double getRadix(int age, string candlesLine) {
	int l=sz(candlesLine), t=1,b=0; g=(double)age;
    v.clear();
    rep(i,l){
      int n=candlesLine[i]-48;
      if (t&&n==0)continue;
      t=0;
      v.pb(n); if (n) b++;
    }
    k=sz(v); reverse(all(v));
    
    if(k==1) return age==1? -2 : -1;
    if(k==0 || b==0) return -1;
    if(k==0) return -1;
    if(b==1) return rt(age,k-1);
    if(age==1 && v[0]==1) return -1; /// ←ここ追加
    double hi=rt(age,k-1), lo=rt(age,k);
    if (hi<lo) swap(hi,lo); lo/=k; hi*=k;
    return md(lo,hi);
  }
};

Medium(450): CandyBox

  • DP
  • D種類C個ずつ、でN=CD([2..5000])個
  • 10000回シャッフル
  • N個から2つ選ぶ nC2 通りのパターンの平均って
    • ((nC2 - n)p_i + ∑p_i)/n みたいに出るので計算は意外と楽
  • 最悪ケースでもTLEしないのを確認してsubmit
  • 235.35pts (34'41'')
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class CandyBox {
  int c,d,cd;
  vector<vector<double> > gen;
  void swapgen(int g){
    int g0=g%2, g1=(g+1)%2, c=cd*(cd-1)/2; // assert(cd > 1)
    double sum=0; rep(i,cd){ sum+=gen[g0][i]; }
    rep(i,cd) {
      gen[g1][i] = gen[g0][i] * (c-cd) + sum;
      gen[g1][i] /= c;
    }
  }
  vector<double> count(int g){
    vector<double> ans(d,0);
    g %= 2;
    rep(i,d) {
      rep(j,c) {
        ans[i] += gen[g][c*i+j] / c;
      }
    }
    return ans;
  }
 public:
  vector<double> expectedScore(int C, vector<int> score, int S) {
    c=C, d=sz(score), cd=c*d;
    gen.resize(2); gen[0].resize(cd); gen[1].resize(cd);
    int e=0; rep(i,d) rep(j,c){ gen[0][e++] = score[i]; }
    rep(i,S) swapgen(i);
    return count(S);
  }
};

Hard(1000): WarTransportation

  • 残り5分。
  • 開いた。
  • 引数をパースして隣接行列つくるところまで

Challenge Phase

  • 250点が撃墜ゲー
    • 20人中15人撃墜される
  • wataさん他部屋の人に何度も撃たれるが生き残る
  • 手に汗握った
  • Challenge生き延びて93位。初の2桁行けるか?

System Test

結果

Room: 4/19

Div1: 62/544

1371→1537 (+166) 何度目だ黄色(…超うれしい)

http://gyazo.com/c8d8f9dab4cf6add9faf7ebf011f8412.png

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