ぽえの競プロノート

最終更新: 2026-05-16 問題へのリンク 問題概要 $N$ 頂点 $0$ 辺の無向グラフと長さ $M$ の数列 $R, B$ が与えられる。 $B$ のすべての並び替えに対して頂点 $R_i$ と頂点 $B_i$ を辺で結んだとき、連結成分の個数の期待値を求めよ。 ・$N \le 17$ ・$M \le 10^5$ 600点 解説 $S = \{1, 2, \dots, N\}$ とする。 連結成分の個数の期待値は、 $f(T) = グラフ内のTに含まれる任意の頂点と連結な頂点集合が T と一致する B の並び替えの個数$ とすることで $\dfrac{1}{M!}\displaystyle\sum_{T\subseteq S}f(T)$ と表せる。 $f(T)$ について考える。 $|T| = 3$ のとき、 $T$ の $1$ つ以上の集合の分割は以下の $5$ 通りがある。 色を入れ替えても影響はないので、左側(頂点番号の最小値)が常に赤になるように入れ替えることができる。 赤色の点が表す部分集合について考えると、 $g(T) = グラフ内のTに含まれる任意の頂点と連結な頂点集合が T に含まれる B の並び替えの個数$ とすることで、 $f(T) = g(T) - \displaystyle\sum_{U\subset T, \min(S) \in U} f(U)g(T\backslash U)$ この式を昇順にdp を適用して計算することで $f(T)$ を決定することができる。 $g(T) = \left(\displaystyle\sum_{i \in T}r_i\right)!$ であるので、 計算量は $\displaystyle\sum_{0 \le i \le N} \dbinom{N}{i}2^i = 3^N$ であるので $O(3^N)$ である。 実装上の注意 $\displaystyle\sum_{i \in T}r_i = \displaystyle\sum_{i \in T}b_i$ であるとき、辺の入次数と出次数が一致しないため、条件を満たす繋ぎ方が存在しないことに注意。 AC コード 提出へのリンク #include <bits/stdc++.h> ...

問題へのリンク 問題概要 $N$ 個の長さ $M$ の数字のリールからなるスロットがあり、毎秒一つ以下のリールが止められる。 リールが示す数字をすべて等しくするためには最短何秒かかるか。 ・$N \le 100$ ・$M \le 10^5$ 600点 解説 この問題は、数字ごとに分けて解くことができる。文字種数を $\sigma$ とする。また、解の上界を考えると、示す数字をすべて等しくすることができるならば $NM$ 秒以下でできることが分かる。 これにより、数字 $k$ と正整数 $T (\le NM)$ に対して次のような問題が与えられる（線形計画緩和を用いた）。 $N$ 行 $T$ 列の行列 $v$ が与えられる。ただし、 $$ v_{i,j}= \begin{cases} 1 & (S_{i,j\%M}=k) \\ 0 & (S_{i,j\%M}\neq k) \end{cases} $$ である。 ・$\sum_{i}x_{i, j} \le 1$ ・$\sum_{j}x_{i, j} \le 1$ ・$0 \le x_{i, j}$ これらを満たす $N$ 行 $T$ 列の行列 $x$ に対して、 $\sum_{i}\sum_{j}x_{i, j}v_{i, j}$ を最大化せよ。 この線形計画問題の答えが $N$ ならば $T$ 秒以下で示す数字をすべて $k$ にすることができることが分かる。また、 $T$ に対して答えに単調性があるので、二分探索をすることで解が分かる。 この問題は次のようなグラフを考えることで、最大流問題として解くことができる。 例えば、$N=3, M=3, T=NM=9, v = \begin{pmatrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0\end{pmatrix}$ を考える。 v に対応するグラフ このようなグラフから、S からG への最大流を求めることになる。 しかし、これだと頂点数 $O(NM)$ 、辺数 $O(NM)$ になってしまう。頂点数 $V$ 辺数 $E$ の辺容量がすべて $1$ のグラフの最大流はDinic 法を用いることで $O(\sqrt{V}E)$...

作成日: 2026-05-13 最終更新: 2026-05-13 問題へのリンク 問題概要 $N$ 頂点の完全グラフから $M$ 辺を取り除いたとき、頂点 $1$ から頂点 $N$ への最短経路の個数を求めよ。 ・ $2 \le N \le 2 \times 10^5$ ・ $0 \le M \le \min(2 \times 10^5, \binom{N}{2})$ 575 点 解説 全頂点に対して頂点 $1$ からの最短距離が分かれば、距離が小さい順に最短経路の個数を決定できる。 頂点 $1$ からBFS をする。このとき、頂点から出ている辺をすべて見るのではなく、未訪問の頂点のうち、辺が存在するものに遷移すれば $O(N)$ 回の遷移で済む。 頂点 $1$ からの最短距離が分かれば、最短距離で頂点をソートして区間加算・一点取得を高速にできるデータ構造を用いて、最短距離が $k$ の頂点から最短距離が $k+1$ の頂点に遷移することで計算できる。加算をする区間は、取得する位置より後にあるので、いもす法を適用して $O(N+M)$ で計算できる。 全体の計算量は $O(M+ N \log{N})$ 。 サンプル $1$ サンプル $2$ (5/14 追記) ソートはバケットソートを用いることで $O(N)$ でできるため、全体の計算量は $O(N+M)$ にすることができる。 実装上の注意 出力する答えが $0$ の時に $-1$ を出力する実装にしていると、答えが $998244353$ の倍数の時にも $-1$ を出力してしまうので、距離の配列などを使って頂点 $N$ まで到達できるかどうかを判定しておくとよい。 AC コード 提出へのリンク #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (ll i=0; i<(ll)(n); i++) const ll mod = 998244353; const int inf = numeric_limits<int>::max()/2; const ll INF = numeric_lim...