SRM603-606 Div1E

・SRM603 Div1E MaxMinTreeGame

各頂点にコストがついている木が与えられる.二人で交互に好きな辺を消して出来た二つの木のうち好きな方を選ぶということを繰り返す.頂点1つだけの木になったら終わりで,その頂点のコストが得点となる.先手は得点を最大化したくて,後手は最小化したい.互いに最善を尽くしたときの得点は?という問題.

状況によって木の形がさまざまなので探索は難しそう.なので一旦ゲームをする気持ちになってかんがえてみると,まず自分の望む頂点の次数が1ならつながっている辺をカットしてその頂点を選べばいいことがわかる.次に望む頂点の次数が2以上の場合どうかとかんがえると,つながっている辺をカットしていっても,次数が1になった時点で相手がその頂点をカットして捨ててしまうので選べないことがわかる.したがって結局先手が次数1の頂点のうち最もコストの大きい頂点を選んでゲームが終わる(かなしい).

・SRM604 Div1E PowerOfThree

頂点(0,0)からスタートして頂点(x,y)まで行きたい.ただしi回目の移動では上下左右のいずれかの方向に3^iだけ進む.目標は達成できるか?という問題.

x,yは負の場合もあるが絶対値をとってx,y≧0としてよい.まずx方向についてかんがえる.3^kだけ進みたければk回目に移動すればよく,2*3^kだけ進みたければk回目とk+1回目に移動すればよいので,xを3進法で表したときの下のケタから見ていくと各回にどう動くべきか決まる.y方向も同じなのでまとめると

x,yが共に3の倍数(一番下のケタが0)ならk回目は両方動かせないのでImpossible

x,yが共に3の倍数でないならk回目は両方動かさないといけないのでImpossible

x,yの片方が3の倍数でないとき,3で割った余りが1なら1を引き,余りが2なら1を足して両方3で割る

ということを繰り返してx,yが共に0になったらPossibleと判定できる.

・SRM605 Div1E AlienAndHamburgers

n個のものがあり,それぞれ美味しさと種類が決まっている.このうちいくつかのものを選んだとき得点は(美味しさの和)×(種類数)で決まる.得点を最大化せよ,という問題.

まず美味しさが0以上であるようなものを選んで損はないので全て選ぶ.残りは美味しさが負のものだが,場合によっては種類数が増えて得点が大きくなるかもしれない.そこで美味しさの大きい順に見ていって,種類数が増えるなら加えるということをしながら得点を計算し,そのうち最大のものが答え.

・SRM606 Div1E EllysNumberGuessing

数当てゲームをする.guess[i]と答えの数との差の絶対値はanswer[i]であることがわかっている.答えが一通りに定まるならその数を,二通り以上あるなら-1を,情報が矛盾している場合は-2を答えよ.という問題.

まず最初の情報だけで答えの候補がguess[i]±answer[i]の二択に絞られてしまう.あと他の全ての情報に矛盾しないかを調べていくだけ.