ABC 254 E — Small d and k

考察

次数が3以下、探索半径kが3以下なので、各問い合わせで距離k以内に現れる頂点数は高々1+3+3²+3³=40程度である。全グラフを前計算するより、問い合わせごとに始点xから深さkまでBFSする。BFSで各頂点の最短距離を確定し、距離0からkまでの頂点番号を一度ずつ合計すればよい。

訪問印は問い合わせごとに初期化せず、今回の探索で触れた頂点だけ戻せる。閉路で同じ頂点へ複数経路から着く場合も、一度だけqueueへ入れる。

典型の発動条件

次数と深さが小さい局所BFS

発動条件: 問い合わせ数は多いが、各問い合わせの最大次数と探索半径が小さいとき。 距離k以内だけBFSし、訪問済み頂点の値を集計する。

触れた要素だけの初期化

発動条件: 一回の探索で訪問配列の一部しか変わらないとき。 今回訪れた頂点を記録し、その印だけを問い合わせ後に戻す。

問題固有の要素

制約の「次数3以下」と「k≤3」は別々ではなく、組み合わせることで一問い合わせの探索量そのものを40程度へ制限する。

別の問題へ持ち帰る視点: 多数問い合わせでも、分岐数^深さが十分小さいなら前計算より問い合わせごとの打ち切り探索が単純で強い。

正当性

BFSは辺数の少ない順に頂点を取り出すため、各頂点を初めて発見した時点の距離が最短距離である。深さkで展開を止めれば距離k以下の頂点を漏らさず、距離kを超える頂点を含めない。訪問印により各頂点番号は一度だけ足されるので、得られる和は問い合わせの答えに一致する。

実装上の注意

  • 距離kの頂点は合計へ含めるが隣接先へは展開しない。問い合わせ間の訪問印を全N初期化せず、今回訪れた頂点だけ戻す。k=0ではxのみを答える。

復習の核

  • 全点BFSとのランダム比較に加え、k=0、次数3の木、三角形など複数経路で同じ頂点へ着くグラフ、孤立頂点を確認する。

計算量と制約

時間

O(N+M+Q·3ᵏmax)、最大次数3、kmax≤3。

空間

O(N+M)、訪問stampと小さいqueue。

制約との対応

公式制約の確認範囲: Time limit: 3.5 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 1.5 \times 10^5; 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2}); 1 \leq a_i \lt b_i \leq N; (a_i,b_i) \neq (a_j,b_j), if i\neq j.; The degree of each vertex in the graph is at most 3.; 1 \leq Q \leq 1.5 \times 10^5; 1 \leq x_i \leq N; 0 \leq k_i \leq 3; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Small d and k の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

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

      主タグ: 有界全列挙・有限case分解

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

      学習の位置

      体系上の位置: 候補数を界して全列挙・有限case分解する

      • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

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

      • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題