解法 どんな文字列でも"A"or"B"or""の3種類のどれかにすることができる。そのため無限にある文字列を"A"にできる文字列、"B"にできる文字列、""にできる文字列の3つのグループに分けることができる。"A"にできる文字列は逆に"A"から作ることができる。"B"、"…

解説 wa = a_iを含む良い集合の和の最小値とすると、 wa - a_i ≧ K <=> a_i は不必要 wa - a_i < K <=> a_i は必要 となる。 全てのカードiについて、カードiを含まないカードで作れる和をdpで調べる。 dp[j][k] = カードjまで調べたときに和kを作れるかどう…

解説 dp[i][j] = i人未満のグループのみで、j人を分ける通り数とする。 このようにdpを定義すると、dpの更新式は以下のようになる。 i人のグループを一個も作らないとき、 残りのN-j人のうち、i人のグループをk個作るとき、 で割るのはグループを区別しない…