問題 問題概要 省略 解法 dpで解いた。直線になっていれば即座にdpだろうなと思ったけど、円になっていたからすぐにわからず苦戦した。円になっている時に注意しなければならないことは、0オリジンで考えた場合、頂点0を選んだ場合、もし頂点n-1も選んだら、…

問題 問題概要 省略 解法 誤差の許容が大きいため、モンテカルロ法を使えばいいらしい。やっていることは、確率pで1枚目を選ぶとあるので、乱数で0~1までだし、pより小さければ1枚目を選び、そうでなければ、その他のものを等しい確率で選ぶというシミュレー…

問題 問題概要 頂点1からnまで達するために、必要な辺の長さの最小値。ただし、最小値は10の倍数 解法 大まかな方針として、必要な辺の長さを求めるので、Xcm以下の辺の長さだけでunion-findを使いグラフを形成して、1からnに達するか(同じ連結成分に含まれ…