Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-24

SRM456 div2 (再チャレンジ)

13:45

Medium - CutSticks

hardに再挑戦です. 多くの人がバイナリサーチを使って解いていたのですが, なぜなのかがわかりませんでした. chokudaiさんのblogをみたところ,

「K番目に長い」=「その長さより長い棒がK本ある」

とあって納得. この発想ができるかどうかが鍵ですね.

まず, 0 - 0e09 の間をバイナリサーチで探索します. sticksを切っていって, 候補の解nよりも長いstickがK本以上作れれば右へ, そうでなければ左へ探索範囲を狭めていきます. ある長さnよりも長いstickの本数を調べる方法は, sticksの各要素についてnで割っていくことで求まります. その際切る回数は最大C回なので, それ以下になるように制限をつけます.

また, バイナリサーチの繰り返し回数は定数にすべきという注意点も今回学べました. 例えば while (n - m < 1e09) などとすると, インプットによっては無限ループになってしまいます. 定番のチャレンジポイントらしいです.

今回chokudaiさんの記事のほかには, ellerさんのblog, nitoyonさんのblogも参考にさせていただきました. ありがとうございました.

class CutSticks {
public:
  double maxKth(vector <int> sticks, int C, int K) {
    double ret = 0;
    double left = 0, right = 1e09, mid = 0;

    for (int i=0; i<1000; i++) {
      mid = (right + left) / 2;

      int number_of_large_stick = 0, number_of_cut = 0;
      int c = C;
      for (int j=0; j<sticks.size(); j++) {
        if (sticks[j] < mid) continue;
        number_of_cut = (int)(max(sticks[j] / mid - 1.0, 0.0));
        number_of_cut = min(number_of_cut, c);
        c -= number_of_cut;
        number_of_large_stick += number_of_cut + 1;
      }

      if (number_of_large_stick >= K)
        left = mid;
      else
        right = mid;
    }

    ret = mid;

    return ret;
  }
};