SRM619-622 Div1E

大学に印刷してきた問題終わってしまった(ア

・SRM619 Div1E SplitStoneGame

n個の石の山がある.i番目の山にはnumber[i]個の石がある.二人で,交互に2個以上の石がある山を選び,その山にある全ての石を異なる二つの山に移すことを繰り返す(分け方は任意だが,どちらの山にも1個以上の石を移さないといけない).自分のターンに行動できなかった方が負け.二人が最適に行動するとき先手が勝つか負けるかを判定せよ,という問題.

最初から2個以上石のある山がない場合は明らかに先手の負け.また,1個以上の石を他の山に移すので操作のあと絶対に2個以上石のある山が存在する.したがって2個以上石のある山がない,というのは最初以外にあり得ない.ということで負けるのは山の数が3個未満になるときだけなので偶奇で勝敗がわかる.

・SRM620 Div1E PairGame

自然数のペア(x,y)を(x+y,y)または(x,y+y)にする操作を繰り返す.上手く操作することで(a,b),(c,d)に出来るようなペア(x,y)のx+yの最大値を求めよ,という問題.

操作を逆に見る.よくかんがえると自然数のペアという条件から1回の操作で(x,y)になるようなペアはx>yのとき(x-y,y),x<yのとき(x,y-x)に限られることがわかる(x=yのときは操作で作ることはできない).したがって操作を繰り返して(a,b),(c,d)になるようなペア(x,y)というのは簡単に列挙できるので共通するものの中でx+yの最大値を求めればいい.

・SRM621 Div1E RadioRange

n個の円がある.i番目の円の中心は(X[i],Y[i])で半径はR[i]である.(0,0)を中心とする円であって全ての円が完全に内側か外側にあるようなものを良い円と呼ぶ.半径を[0,Z]から等確率で選んだときそれが良い円である確率を求めよ,という問題.

半径を0から大きくしていくとある円に触れ始めたり,ある円を完全に包含するようになったりする.各円について半径がmin(中心と(0,0)の距離-半径,0)になるとその円に触れ始め,半径が中心と(0,0)の距離+半径になるとその円を完全に包含する.これらのイベントを半径の小さい順に並べてみていくと良い円になるような区間が求まるのでその区間の長さ/Zが答え.

・SRM622 Div1E BuildingRoutes

n頂点のグラフがあり任意の頂点対(i,j)(i≠j)間に有向辺があり,その長さはdist[i][j]である.各辺について頂点sからtまで最短距離で行くときにその辺が用いられ得るような頂点対(s,t)を数える.これがT個以上の場合,その辺は「あぶない辺」と呼ばれる.全てのあぶない辺の長さの和を求めよ,という問題.

これは簡単.ワーシャルフロイドで全頂点対の距離を求めた上で(頂点s-i間の最短距離)+dist[i][j]+(頂点j-t間の最短距離)==(頂点s-t間の最短距離)であるかを調べればその辺がsからtに最短距離で行くとき用いられ得るかが判定できるので全ての辺についてO(n^2)かけて数えればいい.