UTPC 2011

年々ひどくなっていく...。もうやめたら、ってくらいひどいスコア。実装重め...。

E

N個のタスクが渡される。それぞれのタスクにはかかる時間と、締め切りが与えられるので、締め切りまでに終わらせることができるタスクの数を最大化せよ、という問題。

締め切り順にソートして、K個のタスクが締め切りまでに終わっているとときの、最速時間をメモしてやるだけ。

F

N点の完全グラフから、同じ辺を二度使わずにK個のMSTを作れ、という問題。

K<=N/2ならできる。後は割り当てるだけ...。基本的には各ノードのIDを+1したヤツとつなぐ、+2したヤツとつなぐ、...、+Kしたヤツとつなぐ、なんだけど、変なループができるので調整が必要。