naoya_t@topcoder

SRM462

13:34 |

wataさんと同じ部屋

DIV	level	問題名	競技中	後で	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の問題を開く
• が、戻ってきて適当なテストケースを２，３追加
• "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

• 250点まだまだ落ちる
  • 結局部屋で3人だけ残った。全体でも生存者40人ちょい
• 250,450ともに生き残る
• 62位！初の2桁！

結果

Room: 4/19

Div1: 62/544

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