読者です 読者をやめる 読者になる 読者になる

noyのブログ

プログラミングとかゲームとか

典型探索問題を解く

メモ 競技プログラミング

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

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