naoya_t@topcoder

SRM456 Medium: CutSticks

きょうの復習, 過去問 | 20:46 |

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