問題 解法?（本題とは関係なし） まず、dp[i][j][k] = i 個目まで見て末尾が j で k 個続いているものの個数 として各要素の遷移に かけて全体 のコードができる。 （下記コードのコメントアウト部分に対応） 簡単に思いつく高速化としてほとんどの a は dp[…

問題 解法 「mex を追加する、または mex 以外を追加する」という操作において、種類数という情報だけで遷移元と遷移先を表現できる（情報として十分である）ということに注目する。 dp[i] = 数列の要素が i 種類 とすると mex を追加する場合: 種類数だけで…

解けたのでおまけがメイン。 問題のリンク 概要 与えられた単純無向グラフについて、辺を 本以上取り除くことでいくつかの完全グラフに分割するときの、完全グラフの個数の最小値を求めよ。 解説 個の頂点集合を順に列挙し、それぞれの頂点集合に対し、その…