ABC 281 G — Farthest City

考察

root1からの距離layerを固定すると、各非root頂点は直前layerへのedgeを少なくとも1本持ち、2層以上離れたedgeを持たないことが必要十分である。

vertex Nだけが最遠なので、まず1…N-1を非空layerへ順に配置・配線し、最後にNをその次layerへ単独で接続すれば重複なく数えられる。

採用する候補: 既に配置した通常頂点数nと最新layer size kのDPで、次layerの頂点集合・前layerへの非空edge・layer内edgeをまとめて遷移する。

距離列そのものを列挙せず、次の配線数に必要な最新layer sizeだけへ状態圧縮できる。

棄却する候補: 各頂点のdistance labelを全割当てし、その後全edge subsetがBFS条件を満たすか数える。

distance割当てとedge subsetが指数的で、N≤500に使えない。

次layerにl個選ぶ方法は残りlabelからC(rem,l)、各新頂点の前layer接続は(2^k-1)^l、同layer内edgeは2^{l(l-1)/2}通りで独立である。

全通常頂点を配置後、Nは最新layerの非空subsetへ接続する2^k-1通りだけで、これにより他全頂点より距離が1大きい。

dp[1][1]=1から、remaining=N-1-nの通常頂点よりl≥1を選び、C(remaining,l)(2^k-1)^l2^{C(l,2)}を掛けてdp[n+l][l]へ送る。n=N-1になった各kから(2^k-1)を掛けて合計する。全演算は入力M modulo。

典型の発動条件

BFS layer数え上げ

発動条件: rootからの最短距離条件を満たすlabelled graphを数えるとき。

distance layerを順に作り、直前layerへの非空接続と禁止edgeで特徴付ける。

layer size DP

発動条件: 次遷移が配置済み数とfrontier layerの大きさだけに依存するとき。

個々のlayer頂点ではなく(n,k)へ集約する。

問題固有の要素

最遠vertex Nを最後の単独layerとして後付けすると、『他は全て近い』条件を自然に強制できる。

別の問題へ持ち帰る視点: distinguishedな唯一最遠点を持つgraph数え上げでは、その点を通常layer生成から除外し最後に接続する。

正当性

根1からの距離層を固定すると、層差2以上の辺は禁止され、同層内の辺は自由である。次層の各頂点は直前層への非空接続を持つことが、指定距離を実現する必要十分条件になる。よって層の頂点選択数、直前層との(2^k−1)^l、同層の2^{l(l−1)/2}を独立に掛けられる。頂点Nを最後の単独層へ置けば他全頂点より距離が大きくなり、逆に条件を満たすグラフはこの層分解を一意に持つ。層サイズDPは全対象グラフを一回だけ数える。

実装上の注意

  • 法Mはprimeとは限らないのでfactorial inverseでC(n,k)を作らず、Pascal recurrence等でmod Mの組合せを前計算する。
  • rootをn=1,k=1に含め、通常頂点の残数とdistinguished Nを二重に数えない。

復習の核

  • N=3でroot layer{1}、通常layer{2}、最遠{3}しかないことから答え1を遷移式で再現する。

計算量と制約

時間

O(N³)、配置済数×最新layer size×次layer size。

空間

O(N²)、DP・二項係数・冪。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 500; 10^8 \leq M \leq 10^9; N and M are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Farthest City の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: 組合せ係数・数え上げ

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題