2017-02-06

典型探索問題を解く

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

パラメータそれぞれに注目して解けるか考える。 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が大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
→二分探索でいけそう。
→できた。