https://atcoder.jp/contests/abc248/tasks/abc248_f
前提知識
解説
https://atcoder.jp/contests/abc248/submissions/31047647
全くメジャーな言い回しではないが、連結DPをする。
ただ単に連結性を状態として持つDP。
一般にこの手のDPでは行列累乗を求めることが多いが、この問題ではそこまで要求もしておらず、
かつ、比較的シンプルな連結性の管理なので、連結DPの入門問題としてかなりいい問題。
DP？
連結DPになじみが無い人にとっては、この問題をDPで解くというのがなんともピンとこないかもしれない。
DPテーブルの定義としては、N列ある点の内、「i列目までの辺の有無が決定している」というのを使っていく。
最終的な条件として、グラフが連結であるということと、取り除く辺の本数も聞かれているので、
以下のようなDPを考える。
dp[cu][del][con]
:= cu列目まで辺の有無が決定していて、
既にdel本辺を削除していて、
上と下が連結しているかがcon（0非連結、1連結）
であるような辺の削除の仕方の組み合わせ
さて、cu列目まで確定していて、そこからcu+1列方面（ざっくり→方面）に辺を確定させると考えたときに
既にcu列目までですべて連結していれば、特に条件については問題ない。
しかし、非連結である場合、
連結成分 連結成分 cu+1列目
のように横に連結成分が離れている場合は、それ以降で修復することはできない。
なので、修復可能な場合は
連結成分 cu+1列目 連結成分 cu+1列目
ちょっと分かりにくいかもだけれど、上下に連結成分が離れている場合のみである。
上下と書いたが、
┌――― └― ―
このような感じでも後でつなげればいいので、上下に連結成分が分かれていると考えて問題ない。
よって、連結性についての状態は「0：上下に非連結」か「1：連結」だけを考えればいい。
初期状態
最初は1列目なので、縦の辺を使うか使わないかで判断する。
dp[1][0][1] = 1; dp[1][1][0] = 1;
これは良いかなという感じ。
遷移
コの字で辺を使うかどうかを考える。
ソースコードを見てもらえばわかるが、どの辺を消したかを全通り人力で遷移を書いている。
全部で8通りなので、まだ人力でやれるレベルではあるが、注意しながらやること。
遷移の流れはコメントでソースコードにインラインで追加した。
そちらを見て理解してほしい。
int N, P; int dp[3010][9010][2]; void chadd(int& x, int y) { x = (x + y) % P; } void _main() { cin >> N >> P; dp[1][0][1] = 1; dp[1][1][0] = 1; rep(i, 1, N) rep(del, 0, 9000) { // all -> ng // 2 del -> ‾ // 上だけを残すので、連結状態であることが前提。遷移後は非連結 chadd(dp[i + 1][del + 2][0], dp[i][del][1]); // 2 del -> _ // 同上 chadd(dp[i + 1][del + 2][0], dp[i][del][1]); // 1 del -> ‾| // 上と縦を残す。連結状態であることが前提。遷移後は縦があるので連結になる chadd(dp[i + 1][del + 1][1], dp[i][del][1]); // 1 del -> _| // 同上 chadd(dp[i + 1][del + 1][1], dp[i][del][1]); // 1 del -> ‾_ // 上下を残す。連結かどうかは問わず使えるが、連結状態は継承される chadd(dp[i + 1][del + 1][1], dp[i][del][1]); chadd(dp[i + 1][del + 1][0], dp[i][del][0]); // 0 del -> ‾_| // 全部残す。連結かどうかは問わずに使うことができ、どんな状態でも連結状態になる chadd(dp[i + 1][del][1], dp[i][del][0]); chadd(dp[i + 1][del][1], dp[i][del][1]); } rep(i, 1, N) { if (i != 1) printf(" "); printf("%d", dp[N][i][1]); } printf("\n"); }
