典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。

パラメータそれぞれに注目して解けるか考える。 DPなら、テーブルに何を持つかを全通り考えてみる。

AOJ ALDS1_4-D Search - Allocation

問題概要

数字がn個与えられる。それをk個のグループに分ける。 グループの数字の総和の最大値が最小となるように分ける。

なんか二分探索っぽいキーワードが。

制約

1 ≤ n ≤ 100,000
1 ≤ k ≤ 100,000
1 ≤ w_i ≤ 10,000

考え方

• nに注目
  i番目までの荷物をいれたときの最大値を求めていく、と考えて無理そうなので諦める。 これだと、どの数字をどのグループに入れたかも保持しないとできない。その上遷移もできなさそう。
• kに注目
  グループの数変えても仕方ない。
• 総和の最大値に注目
  総和の最大値がi以下のとき、グループにできる数字の個数、と考える。 iが大きければ、貪欲にグループを作れば良い。
  →総和の最大値を全通り試してグループができるか調べればよい。
  　→二分探索でいけそう。
  　　→できた。