A12 - Printer

入出力

1
2
3
let N,K = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int64
solve N K Ia |> stdout.WriteLine

方針

二つ要点があります. 一つは何回目で実現できるかに関連して二分探索を思いつけるか, 二分探索を思いつけたとしてどう実装するかです.

ここでは後者の二分探索で何をどう調べるか考えましょう. あるm秒目で必要な枚数が印刷できたかどうかを調べる必要があります. 問題設定からその時間までに各i番目のプリンターはm/Ai枚印刷できています. あとはこの総和を取って必要枚数印刷できたか確認します.

解説

命令型の言語ではwhileで処理する方が多いように思います. ここでは再帰関数で処理します. 二分探索はアルゴリズムのどの本にも載っているため細かい解説は省略します.

1
2
3
4
5
6
7
8
  let rec bsearch l r =
    if r<=l then l
    else
      let m = (l+r)/2L
      let s = Ia |> Array.sumBy (fun a -> m/a)
      if K<=s then bsearch l m
      else bsearch (m+1L) r
  bsearch 1L (pown 10L 9)

問題の制約で答えは 10^9 を超えないとあるため, 最大値(最初のr)はr = 10^9に取ればよいでしょう. もちろん1 \leq Aiの仮定からも保証されます.

途中の印刷枚数確認はArray.sumByでmi/aの和を積めば計算できます.