439.1

やるべきことはやって、全然ダメだっただけ。すっきりした。

250

N個の1リットルの水の入った容器が与えられる。同じ容量の容器二つは任意にマージすることができるとするとき、K個以下にマージするにはいくつ1リットルの水の入った容器を追加する必要があるか答えよ、という問題。

要は bit count がK以下になるまで追加するだけ。

500

文字列がいくつか与えられるので、そのうちのいくつかを選んで並べてできる文字列のうち、回文になっているものの数を答えよ、という問題。

放置した。

1000

N個の2部グラフ状の都市が与えられる。左右に分割したとき、枝が交差しないように減らす最小枝群のうち、辞書順で先頭のものを答えよ、という問題。

rank2 の都市が3つ以上ぶら下がった都市についてどこかしらで枝を切らないとダメ。それらがオーバラップするところからグリーディに切ってみたけれど、それだと甘い感じ。

追記: グリーディに切るんじゃなくて、rank2 の都市が3つ以上ぶら下がっている都市だけを抜き出した二部グラフで、最大マッチングのうち辞書順で最初のものをカットして、それから、残ったrank2 の都市が3つ以上ぶら下がっている都市について、いらない枝を辞書順で最初のものからカットするだけみたい。残った都市のいらない枝は、ぶら下がっているrank2 の都市から出てる枝のどれか。