内容 n種類の商品がそれぞれv[i]個ある。 同じ種類の商品は区別しないが、別の種類の商品は区別するとき、これらの商品からM個取り出す組み合わせの数 考え方 dp[i+1][j]:=商品iまで使って個数j個選ぶ組み合わせの数 漸化式は、商品i-1まででj-k個選んで、商…

問題 木が与えられる。 ある頂点を取り除いてできる連結成分の最大のサイズを各頂点について計算する。 N 考え方 木が与えられたらとりあえず適当な頂点を選んで根付き木にして考える。 木DPで、その頂点以下の部分木の頂点数を求める。 これによって子ノー…

問題 n個のパターン文字列が与えられる。パータン文字列は、小文字アルファベットか'*'で構成される長さMの文字列。 '*'の場合は任意のアルファベット1文字にマッチする。 与えられるパターン文字列は、文字列集合Xのどれか1つの文字列にマッチするように作…

組み合わせ回。