SRM462

2010-02-18

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);
  }
};