読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

TopCoder Open 2017 Round1B

Round1Aに出れなかったので出た。

【Easy-WaterAndOxygen】

宇宙船に乗っていて、残っている水と酸素の量が与えられる。
1日に必要な水と酸素の量が与えられるので、
最大であとどのくらい生存できるかを求める。
ただし、水は電気分解することで半分の量の酸素にできるとする。

二分探索した。
i

double maxDays(int remainH20, int remainO2, int costH2O, int costO2) {
  double rh=remainH20,ro=remainO2,ch=costH2O,co=costO2;
  double l=0,r=1e10;
  for(int i=0;i<20000;i++){
    double m=(l+r)/2;
    if(rh<m*ch){
      r=m;
      continue;
    }
    if((rh-m*ch)/2.0+ro>=co*m) l=m;
    else r=m;
  }
  return l;
}
【Med-CoinConstruction】

財布の中にコインが何枚か入っているとする。
その中から1枚以上選んで和を求めた時、考えられる全てのものの集合をSとする。
Sの大きさがちょうどkとなるようなコインの額の組み合わせを1つ求めよ。

1~kまでを作れればSの大きさはkとなる。
2進数で考えればj枚のコインで2^j-1まで作れる。
よってそれに額がk-(2^j-1)のコインを足せば1~kまでを作ることができる。
一応乱数で確かめた。
(なんか使わない関数があると減点されるよみたいなメッセージが出たから本番では消した。)

   vector <int> construct(int k) {
    vector<int> v;
    int t=1;
    for(int i=0;t*2-1<k;i++){
      v.push_back(t);
      t*=2;
    }
    v.push_back(k-(t-1));
    return v;
  }
  void check(){
    srand((unsigned)time(NULL));
    for(int i=0;i<128;i++){
      int k=rand()%1000000+1;
      k=i+1;
      vector<int> v=construct(k);
      set<int> s;
      for(int b=1;b<(1LL<<(int)v.size());b++){
        int tmp=0;
        for(int j=0;j<(int)v.size();j++){
          if((b>>j)&1) tmp+=v[j];
        }
        s.insert(tmp);
      }
      cout<<k<<":"<<s.size()<<endl;
      assert(k==(int)s.size());
      assert((int)v.size()<=20);
    }
  } 
【全体】

143rd 1498 -> 1510 (+12) highest!!
Yellowコーダーになりました。やったぜ。
とりあえずYellow安定を目指します!(ゆくゆくはRedにね…