codeforces Good Bye 2018 E. New Year and the Acquaintance Estimation
問題概要
頂点のグラフ$G$のうち、頂点の次数が数列$a_1,\dots,a_N$として与えられている。$G$が単純無向グラフであるとき、残り1頂点の次数$a_{0}$としてありうるものをすべて答えよ。
制約
- $1\leq N\leq 5\times10^5$
- $0 \leq a_i \leq N$
解法
問題文に貼られたリンク Graph realization problem - Wikipedia から Erdős–Gallai theorem - Wikipedia を見つけることが重要だった。
Erdős–Gallai theorem
$d_0\geq\dots\geq d_N$がある$N+1$頂点単純無向グラフの次数の列となっていることは、次の2条件を満たすことと同値:
- $\displaystyle\sum_{i=0}^N d_i \equiv 0~({\rm mod}~2)$
- $\displaystyle\sum_{i=0}^k d_i\leq k(k+1) + \sum_{i=k+1}^N \min(d_i,k+1) ~~(k = 0,\dots, N)$.
Editorial解
Erdős–Gallai theoremを$a_{0}=0,\dots,N$についてすべて調べると$\mathcal O(N^2)$になってしまう。しかし実は$X<Y$の2数が答えに含まれるとき、$Z \equiv X~({\rm mod}~2)$かつ$X<Z<Y$なる$Z$は答えになる(Good Bye 2018 — Editorial - Codeforces)。従って二分探索の要領で$\mathcal O(\log N)$個の$a_{0}$について、Erdős–Gallai theoremの条件が成立するか確かめれば解ける。$a_{0}$を固定したとき$\mathcal O(N)$で確かめられるので、全体で$\mathcal O(N\log N)$。
Segment tree 解
答えが区間になることが分かっていなくても解ける。$a_0,\dots,a_N$を昇順に並べ替えた数列を$b_0\geq\dots\geq b_N$とする。また、$\displaystyle B_i :=i(i+1) +\sum_{j=i+1}^N \min(b_j,i+1)-\sum_{j=0}^i b_j$とする。すると$\min_{i=0}^N B_i\geq 0$のときErdős–Gallai theoremの条件を満たすこととなる。
例として$N=10, \{a_i\} = \{a_0, 2, 3, 4, 9, 8, 5, 2, 10, 5, 3\}$とし、$a_0$ の値を変えながら計算してみる。色付きは$a_0$を$j-1\to j$に変えたとき値が変化していることを示す。
- $a_0 = 0$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | 4 | 3 | 3 | 2 | 2 | 0 |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | 41 | 44 | 47 | 49 | 51 | 51 |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | 16 | 19 | 18 | 14 | 10 | 7 | 4 | 2 | 0 | 0 |
$\displaystyle B_i$ | -1 | -1 | -2 | -2 | -3 | -1 | 5 | 13 | 25 | 39 | 59 |
- $a_0 = 1$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | 4 | 3 | 3 | 2 | 2 | $\color{red}{1}$ |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | 41 | 44 | 47 | 49 | 51 | $\color{red}{52}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | $\color{red}{10}$ | $\color{red}{17}$ | $\color{red}{20}$ | $\color{red}{19}$ | $\color{red}{15}$ | $\color{red}{11}$ | $\color{red}{8}$ | $\color{red}{5}$ | $\color{red}{3}$ | $\color{red}{1}$ | 0 |
$\displaystyle B_i$ | $\color{red}{0}$ | $\color{red}{0}$ | $\color{red}{-1}$ | $\color{red}{-1}$ | $\color{red}{-2}$ | $\color{red}{0}$ | $\color{red}{6}$ | $\color{red}{14}$ | $\color{red}{26}$ | $\color{red}{40}$ | $\color{blue}{58}$ |
- $a_0 = 2$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | 4 | 3 | 3 | 2 | 2 | $\color{red}{2}$ |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | 41 | 44 | 47 | 49 | 51 | $\color{red}{53}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | $\color{red}{18}$ | $\color{red}{21}$ | $\color{red}{20}$ | $\color{red}{16}$ | $\color{red}{12}$ | $\color{red}{9}$ | $\color{red}{6}$ | $\color{red}{4}$ | $\color{red}{2}$ | 0 |
$\displaystyle B_i$ | 0 | $\color{red}{1}$ | $\color{red}{0}$ | $\color{red}{0}$ | $\color{red}{-1}$ | $\color{red}{1}$ | $\color{red}{7}$ | $\color{red}{15}$ | $\color{red}{27}$ | $\color{red}{41}$ | $\color{blue}{57}$ |
- $a_0 = 3$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | 4 | 3 | 3 | $\color{red}{3}$ | 2 | 2 |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | 41 | 44 | 47 | $\color{red}{50}$ | $\color{red}{52}$ | $\color{red}{54}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | 18 | $\color{red}{22}$ | $\color{red}{21}$ | $\color{red}{17}$ | $\color{red}{13}$ | $\color{red}{10}$ | $\color{red}{7}$ | 4 | 2 | 0 |
$\displaystyle B_i$ | 0 | 1 | $\color{red}{1}$ | $\color{red}{1}$ | $\color{red}{0}$ | $\color{red}{2}$ | $\color{red}{8}$ | $\color{red}{16}$ | $\color{blue}{26}$ | $\color{blue}{40}$ | $\color{blue}{56}$ |
- $a_0 = 4$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | 4 | $\color{red}{4}$ | 3 | 3 | 2 | 2 |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | 41 | $\color{red}{45}$ | $\color{red}{48}$ | $\color{red}{51}$ | $\color{red}{53}$ | $\color{red}{55}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | 18 | 22 | $\color{red}{22}$ | $\color{red}{18}$ | $\color{red}{14}$ | 10 | 7 | 4 | 2 | 0 |
$\displaystyle B_i$ | 0 | 1 | 1 | $\color{red}{2}$ | $\color{red}{1}$ | $\color{red}{3}$ | $\color{blue}{7}$ | $\color{blue}{15}$ | $\color{blue}{25}$ | $\color{blue}{39}$ | $\color{blue}{55}$ |
- $a_0 = 5$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | 5 | 5 | $\color{red}{5}$ | 4 | 3 | 3 | 2 | 2 |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | 32 | 37 | $\color{red}{42}$ | $\color{red}{46}$ | $\color{red}{49}$ | $\color{red}{52}$ | $\color{red}{54}$ | $\color{red}{56}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | 18 | 22 | 22 | $\color{red}{19}$ | 14 | 10 | 7 | 4 | 2 | 0 |
$\displaystyle B_i$ | 0 | 1 | 1 | 2 | $\color{red}{2}$ | $\color{blue}{2}$ | $\color{blue}{6}$ | $\color{blue}{14}$ | $\color{blue}{24}$ | $\color{blue}{38}$ | $\color{blue}{54}$ |
- $a_0 = 6$
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$b_i$ | 10 | 9 | 8 | $\color{red}{6}$ | 5 | 5 | 4 | 3 | 3 | 2 | 2 |
$\displaystyle\sum_{j=0}^i b_j$ | 10 | 19 | 27 | $\color{red}{33}$ | $\color{red}{38}$ | $\color{red}{43}$ | $\color{red}{47}$ | $\color{red}{50}$ | $\color{red}{53}$ | $\color{red}{55}$ | $\color{red}{57}$ |
$\displaystyle i(i+1)$ | 0 | 2 | 6 | 12 | 20 | 30 | 42 | 56 | 72 | 90 | 110 |
$\displaystyle\sum_{j=i+1}^N \min(b_j,i+1)$ | 9 | 18 | 22 | 22 | 19 | 14 | 10 | 7 | 4 | 2 | 0 |
$\displaystyle B_i$ | 0 | 1 | 1 | $\color{blue}{1}$ | $\color{blue}{1}$ | $\color{blue}{1}$ | $\color{blue}{5}$ | $\color{blue}{13}$ | $\color{blue}{23}$ | $\color{blue}{37}$ | $\color{blue}{53}$ |
ここから、$a_0$を$j-1\to j$に変えたとき、 $pos =\displaystyle\sum_{k=1}^N \mbox{1}\hspace{-0.25em}\mbox{l}_{\{a_k\geq j\}}$とすると
- $i=pos,\dots,n$では$B_i$が1減る
- $i=j-1,\dots,pos-1$では$B_i$が1増える
ことがわかる。$B$に上記の変更をした後、$\displaystyle\min_{i=0}^N B_i\geq 0$かどうかを確かめる、という操作を$j=1,\dots,N$について行うことで解ける。これは区間add-区間minのSegment Treeを使うと$\mathcal O(N\log N)$。
解答例
#include <bits/stdc++.h> using LL = long long; constexpr LL LINF = 334ll << 53; constexpr int INF = 15 << 26; namespace Problem { using namespace std; struct RangeMin { using T = long long; T operator()(const T &a, const T &b) { return min(a, b); } static constexpr T id() { return T(LINF); }; }; struct RangeAdd { using T = long long; T operator()(const T &a, const T &b) { return a + b; }; static constexpr T id() { return T(0); }; }; struct Min_Add { using V = RangeMin; using A = RangeAdd; V::T operator()(const V::T &a, const A::T &b, const int &h) { return a + b; }; }; template <typename M> struct LazySegmentTree { using Val = typename M::V::T; using Del = typename M::A::T; typename M::V calc; typename M::A composite; M act; vector<Val> val; vector<Del> delay; int n, height; explicit LazySegmentTree(int size) : n(1), height(0) { while (n < size) { n <<= 1; ++height; } val = vector<Val>(n << 1, calc.id()); delay = vector<Del>(n << 1, composite.id()); } explicit LazySegmentTree(vector<Val> &v) : n(1), height(0) { while (n < v.size()) { n <<= 1; ++height; } val = vector<Val>(n << 1, calc.id()); delay = vector<Del>(n << 1, composite.id()); copy(v.begin(), v.end(), val.begin() + n); for (int i = n - 1; i > 0; --i) { val[i] = calc(val[i * 2], val[i * 2 + 1]); } } void propagate(int k, int h) { val[k] = act(val[k], delay[k], h); if (h > 0) { delay[2 * k] = composite(delay[2 * k], delay[k]); delay[2 * k + 1] = composite(delay[2 * k + 1], delay[k]); } delay[k] = composite.id(); } inline void update(int l, int r, Del v) { update(l, r, v, 1, 0, n, height); } void update(int l, int r, Del v, int k, int a, int b, int h) { if (l <= a && b <= r) { delay[k] = composite(delay[k], v); propagate(k, h); return; } propagate(k, h); if (b <= l || r <= a) { return; } // update(l, r, v, 2 * k, a, (a + b) / 2, h - 1); update(l, r, v, 2 * k + 1, (a + b) / 2, b, h - 1); val[k] = calc(val[2 * k], val[2 * k + 1]); } inline Val query(int l, int r) { return query(l, r, 1, 0, n, height); } Val query(int l, int r, int k, int a, int b, int h) { if (b <= l || r <= a) { return calc.id(); } // propagate(k, h); if (l <= a && b <= r) { return val[k]; } Val vall = query(l, r, 2 * k, a, (a + b) / 2, h - 1); Val valr = query(l, r, 2 * k + 1, (a + b) / 2, b, h - 1); return calc(vall, valr); } }; class Solver { public: int n; vector<LL> a, r, sum; Solver(LL n) : n(n), a(n + 1), r(n + 2), sum(n + 1){}; void solve() { for (int i = 0; i < n; ++i) { cin >> a[i + 1]; } sort(a.rbegin(), a.rend()); for (int i = 0; i <= n; ++i) { r[a[i]] = i+1; } for (int i = n; i >= 0; --i) { r[i] = max(r[i], r[i + 1]); } sum[0] = a[0]; for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + a[i]; } //a[0]=0のときのBを計算 vector<LL> v(n + 1); for (LL k = 0; k <= n; ++k) { LL lhs = sum[k]; LL rhs = k * (k + 1); if (r[k + 1] >= k + 1) { rhs += (r[k + 1] - (k + 1) ) * (k + 1); rhs += sum[n] - sum[r[k + 1]-1]; } else { rhs += sum[n] - sum[k]; } v[k] = rhs - lhs; } LazySegmentTree<Min_Add> seg(v); vector<LL> ans; if (sum[n]%2==0 && seg.query(0, n + 1) >= 0) { ans.push_back(0); } //a[0]を増やしながらErdős–Gallai theoremの条件を確認 for (int i = 1; i <= n; ++i) { LL pos = r[i] ; r[i]++; seg.update(pos, n + 1, -1); seg.update(i - 1, pos, 1); if ((sum[n] + i) % 2 == 0 && seg.query(0, n + 1) >= 0) { ans.push_back(i); } } //output if (ans.size() == 0) { cout << -1 << "\n"; return; } for (int i = 0; i < (int)ans.size(); ++i) { cout << ans[i] << ' '; } cout << endl; } }; } // namespace Problem int main() { std::cin.tie(0); std::ios_base::sync_with_stdio(false); long long n = 0; std::cin >> n; Problem::Solver sol(n); sol.solve(); return 0; }
note
wikipediaの定理の式が1-indexedで、それを見ながら0-indexedで解いていたら大混乱した 。しかもmain testで落ちた。横着しないで0-indexedの式に書き直すべきだった。