9/19 PKU

1848 Tree

木に何本か辺を加えて、すべての頂点がちょうど1つのサイクルに属するようにするには最低何本加える必要があるか、という問題。

この問題は、サイクルなどは関係なく、「木を、共通の頂点を持たない長さ2以上のいくつかの鎖に分割する」問題と考えてよい。
まず木を根付き木にする。そして、dp[i] = (頂点i以下の頂点群に対して問題を解いたときの答え)として木DP。dp[i]を求めるとき、その頂点を通る鎖について、「上から降ってきた鎖をそこで止める場合」、「上から降ってきた鎖を下へ伸ばす場合」、「そこから2方向へ鎖を下ろす場合」がある。それぞれ考えてDP。

1678 I Love This Game!

数字がいくつかある。先手は、a以上b以下の範囲にある数字を一つ選ぶ(x1とする)。ちなみに0 < a < bである。後手は、x1+a以上x1+b以下の範囲にある数字を一つ選ぶ(y1)とする。次に先手はy1+a以上y1+b以下、…として選ぶ。選べなくなったらゲームは終了となる。先手のスコアはx1+x2+…、後手のスコアはy1+y2+…である。先手も後手も(自分の点数-相手の点数)を最大にすることを考えている。両者最善を尽くすとき(先手の点数-後手の点数)を求めよ。

0 < a < bより、選ぶ数字は単調増加。よってDPやるだけ。