はまやんはまやんはまやん

hamayanhamayan's blog

Keep Connect [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) F]

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");
}