リンク : https://csacademy.com/contest/archive/task/connected-tree-subgraphs/statement/ 問題概要 N頂点の木が与えられる。それぞれの頂点に新たにラベル(頂点番号)をつける。1<=k<=Nのすべてのkについて、ラベルが1からkまでの頂点を選んだとき、1から…

リンク : https://csacademy.com/contest/archive/task/partial_ladder_graph/statement/ 問題概要 N2頂点とN+2(N-1)辺のグラフが与えられる。1<=i<=N-1 の頂点iはi+1同士を結んでいる。N<=i<=2N-1も同様である。また、1<=i<=N-1の頂点iと頂点i+(N-1)は結ば…

リンク : https://csacademy.com/contest/archive/task/ball-sampling/ 問題概要 N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。 解説 いわゆる、コンプリート問題と言われ…

リンク : https://csacademy.com/contest/archive/task/amusement-park/statement/ 問題概要 N*Mの行列Aが与えられる。このA[i][j]は座標(i,j)からA[i][j]の確率で座標(i,j+1)に進み、それ以外は座標(i+1,j+1)に進む。このとき、iがNになるときの移動回数の…