1015

グラフと確率が弱いのは自覚しているので(他が強いわけじゃないけど)、PKUに問題を求めて...。昔使ったアカウントでログインできることを確認するのと、ちょっとテストを兼ねて。SRMの昔のあさるのが優先されるので、しばらく続きやる可能性はないけれど。で、昔解けずにいたやつのリジャッジがあったよ、みたいな通知が来ていたので、なんで解けていないのかを確認。問題自体は今思えば簡単だったなぁ...。

N人からM人を選択して、M人の属性Aの値と属性Bの値の合計値について、差分が最小になるようにしたい。同じ差分が達成できるときは、一番合計値の和が大きくなるものを選び、M人のリストを作成する。(複数通りある場合はどれでも良い。)

Nは高々200で、Mは高々20であり、各人の属性Aと属性Bの値はそれぞれ0から20までの整数である。

今何人チェックが終了したかと、何人採用したかと、Aの合計とBの合計の差分でDPする。合計の和が最大になる必要があるのと、リストする必要があることから、合計値と直前に採用した人の値をテーブルに入れる必要があるけれど、二つテーブルに入れるとメモリ上限をあふれるみたいなので、適当にエンコードする必要がある。(実際に試していないけれど、使用量が倍になったらあふれていたと思う。)