ABC 248 F — Keep Connect

考察

2×N ladder を左から作ると、処理済み部分に右端の上下 2 頂点をどちらも含まない連結成分が生じた時点で、以後の辺では再接続できない。

将来全体が連結になり得る frontier 状態は、処理済み部分が連結な状態 0 と、上下の右端を別々に含む 2 成分だけの状態 1 の 2 種類に限られる。

採用する候補: 列 i、削除辺数 j、frontier の 2 状態を持つ DP で、新しい横 2 辺と縦 1 辺の残し方を遷移する。

全 subgraph を列挙せず、将来の連結可能性に必要な frontier connectivity と削除数だけを保持できる。

棄却する候補: 3N-2 本の辺の各 subset を列挙し、削除後に graph が連結か調べる。

辺 subset が指数個あり、N≤3000 では扱えない。

状態 0 からは新しい 3 辺のうち 3 本または任意の 2 本を残すと状態 0、横辺 a_i,b_i の片方だけを残す 2 通りが状態 1 になる。両横辺を消す遷移は過去成分を孤立させる。

状態 1 からは a_i,b_i の両方を必ず残し、c_i も残せば状態 0、c_i を消せば状態 1 になる。

初列は c_0 を残す dp[0][0][0]=1 と、消す dp[0][1][1]=1 で始める。以後 new0[j]=old0[j]+3old0[j-1]+old1[j]、new1[j]=2old0[j-2]+old1[j-1] を P で計算し、最後の dp[N-1][j][0] を j=1,…,N-1 について出力する。

典型の発動条件

frontier connectivity DP

発動条件: 幅が小さい graph を一方向に構築し、連結性を保つ辺選択を数えるとき。

右端上下頂点の連結/分離だけを状態にし、過去だけの成分を作る遷移を捨てる。

個数付き graph DP

発動条件: 構造条件に加えて、選択または削除した要素数ごとの答えが必要なとき。

削除辺数 j を DP 次元に加え、各 3 辺 pattern の削除数だけ shift する。

問題固有の要素

ladder の幅が 2 なので、将来へ接続できる frontier partition は連結か上下分離の 2 状態だけになり、8 通りの局所辺選択が定数個の係数へ畳み込める。

別の問題へ持ち帰る視点: 細い graph の連結性問題では、過去全体ではなく frontier に接する成分分割だけを状態にする。

正当性

各列の処理後、未処理部分と接するのは右端の二頂点だけである。過去の全頂点がその二頂点を含む一成分か、それぞれを含む二成分かを記録すれば、将来の連結可能性が決まる。新列の三辺の採否を全列挙し、frontierから接点を失った成分が生じる遷移を捨てる。一つの辺集合は列ごとの選択を一意に定めるので、削除数を加えたDPは各連結部分グラフを一回だけ数え、最終frontierが連結の状態が答えとなる。

実装上の注意

  • 負の添字 old0[j-1],old0[j-2],old1[j-1] は 0 として扱い、各加算を入力の法 P で取る。
  • 最終的に連結なら削除可能なのは高々 N-1 本なので、その範囲だけ出力し、状態 1 は答えへ含めない。

復習の核

  • 旧状態 0/1 と新しい 3 辺の 8 pattern を小図で分類し、係数 3 と 2、および孤立により捨てる pattern の由来を確認する。

計算量と制約

時間

O(N²)、列×削除数、連結状態は二つ。

空間

O(N)、列方向rolling DP。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 3000; 9\times 10^8 \leq P \leq 10^9; N is an integer.; P is a prime.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Keep Connect の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: frontier/profile DP・境界状態圧縮

主題
  • frontier/profile DP・境界状態圧縮: 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: frontier/profile DP・境界状態圧縮

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: frontier/profile DP・境界状態圧縮

      • 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題