第 6 回ドワンゴからの挑戦状本選 B

B - Harvest Festival

問題

$n$ 頂点 $m$ 辺の単純無向重み付きグラフが与えられる．辺 $i$ の重みは $d_i$ ．さらに，頂点集合の部分集合 $W \subseteq V$ が与えられる．

$S \subseteq V$ に対して， $f(S)$ を「 $W$ のうち， $S$ の任意の頂点からの距離が $l$ 以内である頂点の集合」と定める．より形式的には，以下のように定める．

$f(S) = \{ w \in W \mid \forall v \in S, \; d(v, w) \leq l \}$

各 $T \subseteq W$ について， $f(S) = T$ なる $\emptyset \neq S \subseteq V$ の個数を求めよ¹．

制約

$1 \leq n \leq 10^5$
$0 \leq m \leq 2 \times 10^5$
$1 \leq |W| (= k) \leq 20$
$1 \leq l, d_i \leq 10^9$

考察

まず各 $w \in W$ について，そこから距離 $l$ 以内の頂点集合を $U_w$ とする．これは Dijkstra 法により $O(k (n + m) \log m)$ で求まる．

これを拡張して， $T \subseteq W$ について， $U_T = \bigcap_{w \in T} U_w$ と定める．つまり $U_T$ は「 $T$ の任意の頂点から距離 $l$ 以内の頂点集合」である．

すると，任意の $S \subseteq U_T$ について $f(S) \supseteq T$ が成り立つ．しかしこれは「ぴったり」，つまり $f(S) = T$ になっていない．それでもこれは メビウス変換 によって「ぴったり」にできる．

具体的には， $f(S) \supseteq T$ を満たすものから $f(S) \supsetneq T$ を満たすものを抜けばいい．言い換えると， $U_T$ から各 $T' \supsetneq T$ について $U_{T'}$ を抜けばいい．よって $|U_T|$ さえ求まっていれば， 高速メビウス変換 によって $O(k 2^k)$ で解が求まる．

$|U_T|$ を求めるアルゴリズムとして，「各 $v \in V$ について $X_v = \{ w \subseteq W \mid d(v, w) \leq l \}$ を求め，各 $T \subseteq X_v$ に対して $|U_T|$ を増やす」という方法を考える．そのままでは $O(n 2^k)$ で間に合わないのだが，

各 $v \in V$ について $|U_{X_v}|$ を 1 増やす．
これに対して(上位集合の) 高速ゼータ変換 を行う．

とすることで $O(nk + k 2^k)$ に落ちて間に合う．

実装例

提出 #9964494 - 第6回ドワンゴからの挑戦状本選

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
#include <tuple>

using lint = long long;

// modint
template <int MOD>
struct ModInt { ... };

constexpr int MOD = 998244353;
using mint = ModInt<MOD>;


// graph
template <class Cost = int>
struct Edge { .. };

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

// dijkstra
template <class T>
using MaxHeap = std::priority_queue<T>;
template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

constexpr lint INF = std::numeric_limits<lint>::max();

template <class Cost>
std::vector<Cost> dijkstra(const Graph<Cost>& graph, int s) { ... }

// main
void solve() {
    int n, m, k;
    lint l;
    std::cin >> n >> m >> k >> l;

    std::vector<int> ws(k);
    for (auto& w : ws) std::cin >> w;

    Graph<lint> graph(n);
    while (m--) {
        int u, v;
        lint d;
        std::cin >> u >> v >> d;
        graph[u].emplace_back(u, v, d);
        graph[v].emplace_back(v, u, d);
    }

    std::vector<std::vector<lint>> dist(k);
    for (int i = 0; i < k; ++i) dist[i] = dijkstra(graph, ws[i]);

    std::vector<int> cnt(1 << k, 0);
    // cnt[T] = T中の全ての街から距離l以内の街の数
    for (int v = 0; v < n; ++v) {
        int b = 0;
        for (int i = 0; i < k; ++i) {
            if (dist[i][v] <= l) b |= (1 << i);
        }
        ++cnt[b];
    }

    // 上位集合に対する高速ゼータ変換
    for (int i = 0; i < k; ++i) {
        for (int b = (1 << k) - 1; b >= 0; --b) {
            if ((b >> i) & 1) {
                cnt[b ^ (1 << i)] += cnt[b];
            }
        }
    }

    std::vector<mint> xs(1 << k);
    for (int b = 0; b < (1 << k); ++b) {
        // 選ばられるべきは，cnt[T]個の頂点集合の部分集合で空でないもの
        xs[b] = (mint(2).pow(cnt[b])).val - 1;
    }

    // 上位集合に対する高速メビウス変換
    for (int i = 0; i < k; ++i) {
        for (int b = 0; b < (1 << k) - 1; ++b) {
            if (((b >> i) & 1) == 0) {
                xs[b] -= xs[b | (1 << i)];
            }
        }
    }

    int ans = 0;
    for (int b = 0; b < (1 << k); ++b) {
        ans ^= xs[b].val;
    }

    std::cout << ans << std::endl;
}

実際は $\bmod 998,244,353$ を取ったものの XOR を出力する． ↩︎