605.1

今日のコードは特にひどかった...。

250

ものの種類と価値が与えられる。満足度の総和を、種類の数と価値の総和の積と定義するとき、すべての部分集合からさ偉大の満足度を答えよ、という問題。

取り敢えず種類ごとにマージ。1個以上選んだときの総和の最大値を計算する。後はそれをソートして、大きい方から順に追加していきつつ満足度計算してやるだけ。

450

N個の整数を、二つのグループに分ける。ソートしたときに、先頭から一個ずつ見ていったときに、それぞれの差分がK以上であるようにしたい。何通りあるか答えよ、という問題。

取り敢えず順番に詰めていくことを考える。結局、K個以上前のヤツに関してはどう入っていても問題にならないので、適当に直近K個の状態を覚えておきつつ探索すれば通った。最適化の余地はありそう。

1000

見てない。