ABC 299 E — Nearest Black Vertex

考察

条件(p_i,d_i)は「黒頂点までの最短距離がちょうどd_i」である。dist(p_i,v)<d_iの頂点は強制白、dist(p_i,v)=d_iには少なくとも一つ黒が必要と分ける。黒候補を減らして得をする条件はないため、全強制白の和集合だけを除いた最大集合を黒にすればよい。

各p_iからBFSしてdist_i[v]を求める。全頂点を黒候補で初期化し、全iについてdist_i[v]<d_iを満たすvを白へする。この除外を全条件で終えてから、全iについてdist_i[v]=d_iの黒候補が少なくとも一つあるか調べる。あればYesと候補の01列、なければNo。条件ごとに一つの黒を先に選ぶ方法では、後の条件から白を強制されるのでこの二段階が必要である。

問題には黒を少なくとも一個置く条件もある。K=0では除外せず全黒を返す。K>0で全距離球に黒があれば自動的にこの条件も満たす。d_i=0では禁止球が空で、p_i自身が黒でなければならない。

典型の発動条件

最大許容集合の構成

発動条件: 禁止条件が要素ごとの除外、要求条件が存在量化。

禁止されない全頂点を採用して存在条件を検査する。

全点対最短距離

発動条件: N,M≤2000の無重みgraphで多数距離条件。

各頂点BFSを前計算する。

問題固有の要素

黒候補を減らす利点がない単調な存在条件なので、最大候補集合一つだけ試せばよい。

別の問題へ持ち帰る視点: 禁止集合を除いた全採用が存在制約のcanonical witnessになる。

正当性

条件(p_i,d_i)があると距離<d_iの頂点は必ず白でなければならない。全条件で強制白となる頂点だけを白とし残りを全て黒にするのが、黒へできる最大集合である。この最大集合に距離d_iの黒が一つあれば条件を満たし、なければどの合法色分けでも新しい黒を追加できず不可能。

実装上の注意

  • d_i=0では禁止ballが空でp_i自身が黒必要。K=0でも黒1個以上の条件を満たす配置を出す。

復習の核

  • 小graphの全着色と比較し、d=0、禁止領域が全頂点、複数条件の境界球が重なる例を確認する。

計算量と制約

時間

K個の指定始点だけからBFSすればO(N+K(N+M)+KN)、保持O(N+M+KN)。全N始点を前計算する方式ならO(N(N+M)+KN)。

空間

O(N+M+KN)。隣接listとK始点の距離表。全N始点を前計算する実装ならO(N²+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2000; N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace; 1 \leq u_i, v_i \leq N; 0 \leq K \leq N; 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N; 0 \leq d_i \leq N; The given graph is simple and connected.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Nearest Black Vertex の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 成立証明から構成解を復元する

主題
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    主タグ: 構成解・witness復元

    補助タグ: 最短路モデル

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

    学習の位置

    体系上の位置: 成立証明から構成解を復元する

    • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

    先に読む単元:

    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

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

    • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題