No.198 キャンディー・ボックス2〜三分探索〜

Quiz

https://yukicoder.me/problems/no/198

Submit

https://yukicoder.me/submissions/335991

解法

  • キャンディーの目的値を決めると操作回数が決まり、これは下に凸の関数になる
  • 三分探索すればいい

学び

    while(right-left>3){
        ll p0 = (2 * left + 1 * right) / 3;
        ll p1 = (1 * left + 2 * right) / 3;
  • AC後、srupさんの記事を参考に自分のコードを洗練させた
  • 具体的には上記
    • whileループの条件はleft, rightが十分に近づいたとき
      • これは二分探索のときも同様に書けばいい
        • while(left+1 != right)
    • p0, p1の決め方には平均値を使っている。doubleが出てこなくて良い