1日目 Yokan Party ★4 (競プロ典型90問)

[問題]

問題文は以上の通り。　画像は E8さんのTwitterから拝借。

問題の概要は、「K+1個にバラす時、全てがx以上となる最大のxを見つける」というもの。言い換えれば、最小値の最大値(限界、境界)を見つけるものだ。

なぜ最小の最大 or 最大の最小　は二分探索なのか

なぜこういう類の問題はにぶたんなのか、自分の思考を整理する。

この問題だと、例えば　ばらした最小のピースの大きさが 1以上 であるようにはできる。ポイントは、 1であるように　ではなくて 1以上であるように という部分だ。

欲しいのは Xであるように　だが、 X以上であることができる最大のXを見つけることができれば、それはXであるようにできるということになる。　なぜなら、 全てのピースがX以上であることができるが、(X+1)以上であることができない　のならば、最小のピースはXである　からだ。

 {OK,OK,OK,OK,OK,OK,OK,OK,ng,ng,ng,ng,ng,ng,ng}

上の図の、境界である OKを効率よく見つけられるのができるのが、ご存知二分探索だ。