hotpepsiの練習帳

SRM 603

着想 | 23:49

Div1 Easy (250) MaxMinTreeGame

問題

• 頂点と辺からなる木が与えられる
• それぞれの頂点には点数がある
• 2人のプレーヤーが交互に辺を一つ選び除去する
• 分離された一方を残し、もう一方を消す
• 残りが頂点一つになったとき、その頂点の点数がスコアとなる
• 先手が点数を最大化、後手が点数を最小化しようとするとき、先手の点数の最大値を求める

方針

• 愚直にメモ化DFSっぽい何かを提出
• Failed System Test
• 後手は任意の葉を選択できる
• なので、先手は葉でない頂点を選ぶのは意味がなく、葉の最大を選択するのが最善
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_603/MaxMinTreeGame.cpp

結果

x-- 0pt 442nd/608 rating 1301 -> 1247 (-54)

思考力不足

http://togetter.com/li/612995