パイプを切り出そう (paizaランク A 相当)
解説
解き方を思いつくところが難しかったです。
解き方の流れ
切り出すパイプの長さを決める(長さの範囲の両端の真ん中mid)
→決めた長さで、A_1からA_nまで順に切り出し、本数を合計する
→切り出した本数の合計がk本切り出せているか判定する
→その判定により両端の範囲を狭める
→求められる誤差まで繰り返す。
解き方を思いつくまで
ある長さで、n本のパイプ1本1本から切り出す。切り出した本数がわかる。それがk本に満たないなら、もっと短い長さにする。k本を超えるなら、もっと長くできる。
できるだけ長くしたいので、k本切り出せるか切り出せないかの境目の長さが知りたい。手間がかかりそうなので、速い処理ができないか。二分探索が使えそう。
長さxのパイプをk本切り出せるなら、それ以下の長さのy(数式で表すとy<=x)についても、もちろん切り出せる。なので、yについては考えなくて良いので、範囲を一気に狭められる。
反対に、長さxのパイプをk本切り出せなかったら、それ以上の長さのz(数式で表すとx<=z)についても、もちろん切り出せない。なので、zについては考えなくて良いので、これも範囲を一気に狭められる。
切り出す長さを短くするほどたくさん切り出せる。長くするほど切り出す数が少なくなる。
こういった単調な性質があるので、パイプの長さで二分探索ができる。
方針:二分探索する
この問題について、パイプの長さの範囲は1 ≦ A_i ≦ 10,000。なので、この範囲を含む(left=)0 ≦ A_i ≦ 10,001(=right)において、二分探索をします。
両端の真ん中の長さmid=(rigth+left)/2のパイプをk本切り出せるかチェックします。
k本切り出せるかチェックの方法は、それぞれのパイプからmidの長さのパイプを切り出し、それぞれの本数を合計した本数がkより小さいか(または大きいか)で、できます。
i番目のパイプから切り出した長さmidのパイプの本数は、A_iをmidで割った商で求められます。これをn本について計算し、合計本数を求めます。
この合計本数がk本に到達しているか判定します。
k本に到達していないなら、切り出すパイプの本数を増やさないといけないので、切り出すパイプの長さを短くします。これより長い長さはk本に到達しないので調べる必要はありません。よって、調べた長さmidを、次から調べる範囲の右端rightにします。
反対に、k本に到達していたら、パイプの長さを長くできます。これより短い長さは調べなくて良いので、midを左端leftにできます。
この流れを、絶対誤差が 10^-6 (0.000001) 以下になるまで繰り返しますが、本条件では50回繰り返せば満たされます。
解答例(Python3とC++の場合参考)
方針では 50 回としていたところを、万全を期すために 100 回にしています。
長さ x のパイプから切り出せる長さ mid のパイプの本数は Math.trunc(a / mid) 本になります。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [n, k] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);
//切り出すパイプの長さを二分探索する
let [left, right] = [0, 10001];//探索するパイプの長さの範囲の両端
for (let i = 0; i < 100; i++) {
/*相対誤差または絶対誤差が 10^-6 (0.000001) 以下であれば正解なので、
50回も繰り返せばよいが、万全を期すため、100回繰り返す */
//長さmidのパイプを合計num_of_pipes本切り出す
let mid = (left + right) / 2;//範囲の両端の真ん中の長さ
let num_of_pipes = 0;//合計何本切り出せたか
//それぞれのパイプの長さについて切り出していく
for (let a of A) {
num_of_pipes += Math.trunc(a / mid);
/* a/midで切り分け、
長さmidに満たない切れ端はいらないのでMath.truncで切り捨てる
求めた本数Math.trunc(a / mid)を、
合計本数num_of_pipesに加えていく */
}
//求まった合計本数num_of_pipesが、k本切り出せたかチェックする
if (num_of_pipes < k) { //k本に満たない＝長さをもっと短くして本数を増やす
right = mid;//midより長い長さはもちろん本数が足りないので、範囲の長い方(右端)をmidまで狭める
} else { //k本切り出せた＝長さをもっと長くできる=本数減らせる
left = mid;//midより短いところはもちろんk本切り出せるので、短い方(左端)の範囲をmidまで狭める
}
}
//100回探索して、切り出せるか切り出せないかのパイプの長さの境目
console.log(left);