Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-23

SRM456 Medium: CutSticks

| 20:46 | SRM456 Medium: CutSticks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Medium: CutSticks - naoya_t@topcoder SRM456 Medium: CutSticks - naoya_t@topcoder のブックマークコメント

  • なんか最初単峰性の何かを想像してて、どこで最大になるか求めようとしていた
  • 既存の棒の長さを順番に試していって、どこまで行けるか(というか求める値がどことどこの間か)という問題に脳内修正
  • ということは要は任意の値でどこまで行けるか、に脳内修正
  • ま、二分探索さ。最初から分かっていたさw
  • どこまで「何が」行けるかの計算に悩んでてごにょごにょしてるうちに時間切れ
  • Challenge Phase無視
  • Practice room
    • 最初の棒の本数(N)が多いときに変な値が出る → 二分探索の最小値が小さすぎて、割り算した結果がINT_MAXより大きくなる → 無限大表現に INT_MAX/N を使うか(※素直にlong longにしとけばいいものを)
    • 最初の本数が少ないときに小さい値が出る → 大きい棒を切ることで順位が変わるのにstick[K](※並べ替え済)を返していた。お馬鹿
    • Cが大きいときに変な値が出る →そろそろlong longにしないと無理ですか
    • 答えが1e8みたいに大きくなる時に二分探索が止まらない → 終了条件がhi-lo>1e-9とか駄目ですってば
    • 5度目の正直でpassed
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define sz(a)  int((a).size())

class CutSticks {
  ll N, C, K;
  vector<double> s;  
 public:
  int f(double x){
    ll cutcnt=0,sum=0;
    rep(j,N){
      double sx = s[j]/x;
      ll cut;
      if (sx >= (double)INT_MAX) cut = INT_MAX;
      else cut=(ll)sx;
      if (cut==0) continue;
      if (cut>=2) cutcnt+=(cut-1);
      if (cut>=1) sum+=cut;
    }
    if (cutcnt >= C) sum -= cutcnt-C;
    if (sum>=K) return 1;
    return 0;
  }
  double md(double l, double h) {
    if (!f(l)) return -1;
    if (f(h)) return h; //-2;
    double m=(l+h)/2;
    if ((h-l)/h < 1e-12) return m;
    if (f(m)) return md(m,h);
    else return md(l,m);
  }
  double maxKth(vector<int> sticks, int c, int k) {
    N=sz(sticks); C=c; K=k;
    sort(all(sticks)); reverse(all(sticks));
    s.resize(N); rep(i,N) s[i]=(double)sticks[i];
    return md(1e-12,s[0]);
  }
};

rng_58rng_582009/12/24 19:36C = 2 のとき、奇数なら1を足す関数
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします

n4_tn4_t2009/12/25 11:49問題作成者様直々にコメントありがとうございます!!
なるほどそういうのもアリですね。頭固かったです。

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