きままにものづくり

日々の気付いたことなんかを書いてます。

SRM603Div1Easy

問題

コストを持つN個のノードとN-1個のエッジを持つツリーが与えられ、二人のプレイヤーで行うゲームを考える。プレイヤーは1つのエッジを選び、そのエッジとそれにより2つに分割されるどちらかのサブツリーを削除する。最後に残ったひとつのノードのコストがゲームのコストとなる。初めのプレイヤーはコストを最大化したく、次のプレイヤーは最小化したい。お互いが最適な戦略をとった場合の結果を求めよ。

解法

リーフの最大値が結果となる。
二人のプレイヤーの目的は正反対なので、最初のプレイヤーが親となっているノードを最後に残したい場合、次のプレイヤーはそのノードを削除したいということになる。反対も同様であるため、最適な戦略は自分のターンで必ず終えることができるノードを選択することになる。よって、最初のプレイヤーは最大化したいので、リーフの最大値が答えとなる。

計算量

 O(N)

コード