ABC155: F – Perils in Parallel 解説

ABC の F 問題の中でもかなり difficulty が高い,AtCoder Beginner Contest 155: F - Perils in Parallel を解説します.

公式解説とは結構違う思考過程ですが,最終的に得られる解法は同じです.

前提知識

以前記事にした知識を使うので,簡単に復習します.
以前の記事: 接続行列を係数にもつ線形方程式

グラフの接続行列というものがあります.これは,行列の行に頂点,列に辺を対応させたものです.各列はちょうど $2$ つの非ゼロ成分を持ち,それらが辺の始点と終点に対応しています.

線形方程式は行列 $A$ とベクトル $b$ を使って $A x = b$ と表されます.解 $x$ を求めるためにガウスの消去法など一般的なアルゴリズムを使うと,$\Theta(NM^2)$ 程度の時間がかかります($A$ を $N \times M$ 行列としました).ただし,係数行列 $A$ がグラフの接続行列である場合は,特別なアルゴリズムを使うことで $O(N + M)$ 時間で解けます.

このアルゴリズムはなかなか役に立つので,ライブラリ化しておくのがお薦めです.詳細は上の記事を参照してください.

考察過程

  • $\mathbb{F}_2$ 上($\mathrm{mod}\ 2$ の世界)の線形方程式に帰着されそう → された
  • $N = 10^5$ サイズの線形方程式なんて良い構造がないと解けない → グラフの接続行列を係数にもつ線形方程式に変形できる? → できた

と,上の前提知識を使うとかなりスムーズだと思います.

解法

$\mathbb{F}_2$ 上の線形方程式としての定式化

以下,全て 0-indexed で書きます.

まず,爆弾を座標でソートし,$A_0 < A_1 < \dots < A_{N-1}$ としておきます. すると,コード $j$ を切ったときにオン・オフが切り替わる爆弾の番号は,$1$ つの区間になります.区間の左端・右端は二分探索で求まり,以降座標の情報は必要なくなります.

ここからは具体例で考えましょう.$N = 5,$ $M = 6$ とします.例えば,

  • コード $0$ を切ると,爆弾 $i \in [1, 4)$ の,
  • コード $1$ を切ると,爆弾 $i \in [0, 2)$ の,
  • コード $2$ を切ると,爆弾 $i \in [1, 2)$ の,
  • コード $3$ を切ると,爆弾 $i \in [1, 5)$ の,
  • コード $4$ を切ると,爆弾 $i \in [3, 3)$ の,
  • コード $5$ を切ると,爆弾 $i \in [0, 4)$ の

オン・オフが切り替わるとしましょう.このとき,全ての爆弾の電源をオフにするために切るコードの組み合わせを求めるには,$\mathbb{F}_2$ 上で線形方程式\begin{equation}\label{lin-equ}\begin{bmatrix}0 & \red{1} & 0 & 0 & 0 & \red{1}\\\red{1} & \red{1} & \red{1} & \red{1} & 0 & \red{1}\\\red{1} & 0 & 0 & \red{1} & 0 & \red{1}\\\red{1} & 0 & 0 & \red{1} & 0 & \red{1}\\0 & 0 & 0 &\red{1} & 0 & 0\end{bmatrix}\begin{bmatrix}x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5\end{bmatrix}=\begin{bmatrix}B_0 \\ B_1 \\ B_2 \\ B_3 \\ B_4\end{bmatrix}\end{equation}の解 $[x_0, x_1, x_2, x_3, x_4, x_5]^\top$ を求めればよいです.係数行列の第 $i$ 行が爆弾 $i$ に,第 $j$ 列がコード $j$ に対応しています.各列で $1$ が立っている箇所は,もちろん $1$ つの区間になっています.

係数行列のスパース化

方程式 \eqref{lin-equ} の係数行列は,一般には密(非ゼロ成分が多い)であり,このままでは方程式を解くのに時間がかかります.係数行列をスパースにするために,左から適当な行列をかけることを考えます.

$1$ が立っている箇所が区間になっている場合は,差分・累積和の関係に注目すると上手くいくことが多いです(競プロ界隈で俗に imos 法と呼ばれるやつです).そこで,式 \eqref{lin-equ} に左から差分行列\[P =\begin{bmatrix}1\\-1 & 1\\& -1 & 1\\&& -1 & 1\\&&& -1 & 1\\\end{bmatrix}=\begin{bmatrix}1\\1 & 1\\& 1 & 1\\&& 1 & 1\\&&& 1 & 1\\\end{bmatrix}\]をかけます.すると\begin{equation}\label{lin-equ2}\begin{bmatrix}0 & \red{1} & 0 & 0 & 0 & \red{1}\\\red{1} & 0 & \red{1} & \red{1} & 0 & 0\\0 & \red{1} & \red{1} & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\\red{1} & 0 & 0 & 0 & 0 & \red{1}\end{bmatrix}\begin{bmatrix}x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5\end{bmatrix}=\begin{bmatrix}B_0 \\ B_0 + B_1 \\ B_1 + B_2 \\ B_2 + B_3 \\ B_3 + B_4\end{bmatrix}\end{equation}となり,係数行列の各列の非ゼロ成分は高々 $2$ つになります.$2$ つの非ゼロ成分は,区間の左端・右端に対応しています.

行列 $P$ は下三角かつ対角成分が非ゼロで,これは正則行列なので,方程式 \eqref{lin-equ} の代わりに \eqref{lin-equ2} を解くことが正当化されます.

係数行列をグラフの接続行列に

方程式 \eqref{lin-equ2} の係数行列は「ほとんど」グラフの接続行列ですが,非ゼロ成分をちょうど $1$ つ持つ列があるのが少し厄介です.そのような列がなければ,接続行列と見なすことができます(非ゼロ成分が $0$ 個の列は自己閉路と解釈できるので OK).

上の具体例で非ゼロ成分数が $1$ つになってしまう理由を考えます.式 \eqref{lin-equ} の係数行列の一番下の行に $1$ が立っているのが原因のようです.ここから,「番兵」として $N$ 番目の爆弾で $(A_N, B_N) = (\infty, 0)$ であるものを追加して考えればよいと気づきます.

こうすると,式 \eqref{lin-equ2} に対応する式は\[\begin{bmatrix}0 & \red{1} & 0 & 0 & 0 & \red{1}\\\red{1} & 0 & \red{1} & \red{1} & 0 & 0\\0 & \red{1} & \red{1} & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0\\\red{1} & 0 & 0 & 0 & 0 & \red{1}\\0 & 0 & 0 & \red{1} & 0 & 0\end{bmatrix}\begin{bmatrix}x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5\end{bmatrix}=\begin{bmatrix}B_0 \\ B_0 + B_1 \\ B_1 + B_2 \\ B_2 + B_3 \\ B_3 + B_4 \\ B_4\end{bmatrix}\]となり,無事係数行列の全ての列が $0$ 個または $2$ 個の非ゼロ成分を持つようになります.

あとはこの方程式を「接続行列を係数にもつ線形方程式」のライブラリに投げれば,答えを得ることができます.

解法全体の計算量は,最初のソートと二分探索がボトルネックとなり,$O((N+M) \log N)$ です.
AC コード (C++)

タイトルとURLをコピーしました