TCO 2012 Round 2B

配点詐欺。

300

ダーツのボードがあるが、スコアが消えて分からなくなっている部分がある。確実に狙ったところに当てられるときに、目的の点数を達成する最小回数を答えよ、という問題。

見えている最大値を狙うか、分からない部分を全部一回ずつ狙うか。後者の場合は小さい数字が順番に割り当てられていくと考える。取り敢えず二つの場合で良い方を選択するので、最後の調整以外は一意に決まる。

550

二人でN冊の本のうち、K冊の本を持っていくことを考える。最初にK冊を取って相手に渡す。以降指定された冊数だけ手持ちの本を相手に渡すという処理を交互に行って、最終的に相手の本と自分の本の重さの差分をできるだけ大きくしたい。また、可能であればできるだけ本の重さの総和を大きくしたい。最終的に二人が持っていく本の重さをそれぞれ答えよ、という問題。

K冊の本の選び方が決まってしまえば、後は重たい順に渡すのが最善。なので、K冊をソートしたときに何番目を持つかが決まる。後は、N冊をソートして、DPしてやればおしまい。

900

見てない。