問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=（i回スワップした後にbに移動している確率…

問題 コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1～Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。 やりかた 公式解説を参考にしました。 ある時点で選んだコインの総…

問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである（要は閉路がない）。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征…