1505

整数配列でタスクの大きさが与えられる。K個の連続するタスクに分割するとき、一つの連続するタスクに含まれるタスクの合計が最大のものを最小にするような分割を答えよ、という問題。連続するタスクには少なくとも一つのタスクが含まれる。複数の分割が可能な場合は、辞書順で先頭のものを答える。

取り敢えず一番大きい連続するタスクの合計値をバイナリサーチで求める。最大の大きさがNで可能かどうかは、N以下である限りGreedyにタスクを割り当てたときの、分割がK個以下であるかどうか。

先頭から一個だけをタスク群として残りがK-1個のタスク群になるか、ならないなら2個のタスク群にして残りがK-1個のタスク群になるか、という感じに再帰的にやるだけ。1個以上なのでdo文を使ってやれば、バイナリサーチの判定ルーチンを再利用できることもあって、結構すっきり書ける。分割方式の決定は多分綺麗に書けるように意図しているので、手習いとしては非常に良問だと思う。出力形式がちょっと面倒な気もするが...。