ぽえの競プロノート

問題へのリンク 問題概要 $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)$...