問題 問題概要 N個のノードのグラフの全点間最短距離A_ijが与えられる. これを満たすような辺の張り方は存在するか.あるなら辺のコストの総和を求めよ. 1 <= N <= 300, 1 <= A_ij <= 109 解法 各頂点間について,A_ijの辺があるか,辺が存在しないかのいずれか…

問題 問題概要 2つの山にX,Y個の石が置かれている. プレイヤーは一つの山から2i個(2<=2i<=XorY)とってもう片方の山にi個置くことができる. 石が取れなくなったら負け. どちらのプレイヤーが勝つか. 1 <= X,Y <= 1018 解法 とりあえず実験してみる. X<=1 & Y …

問題 問題概要 A(x1,y1), B(x2,y2), C(x3,y3)が与えられる. ABC内部に半径の同じ円を2つ描く時,最大の半径を求めよ. 解法 BC,CA,ABをそれぞれa,b,cとする. またcが最大の辺とする. 内接円の中心O,半径r, 内部に描く二つの円の半径をxとすると,以下のようにな…