Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 258 G問題 Triangle

AtCoder ABC ABC258 G問題 600 pts

問題

提出解答

問題の概要

$N$ 頂点からなる単純無向グラフ $G=(\{1,2, \dots, N\},E)$ の接続行列 $A$ が与えられる. この $G$ にある三角形の個数を求めよ.

つまり, 以下を満たす整数の組 $(i,j,k)$ の個数を求めよ.

$1 \leq i \lt j \lt k \leq N$
$ij, jk, ki \in E$

制約

$3 \leq N \leq 3000$
$A$ は単純無向グラフ $G$ の接続行列

解法1 (正解を求める)

数え上げの答えを考える. 辺 $e=xy \in E$ を含むような $G$ に存在する三角形の個数を求める. このとき, $z \in G$ が $e$ を含む三角形の残りの1頂点になりうることの必要十分条件は $z$ が $x,y$ の共通近傍であることである.

つまり, $v \in V$ の近傍全体の集合を $N_G(v)$ とした時, 1つの三角形について上の方法だと3回カウントされることから, 求めるべき解答 $X$ は

$\displaystyle X:=\dfrac{1}{3} \sum_{e=xy \in E} \# (N_G(x) \cap N_G(y))$

である.

ここで, 各 $e=xy \in E$ に対して $\# (N_G(x) \cap N_G(y))$ を求めるためには $O(N)$ 時間かかってしまい, $G$ の辺の数を $M$ とすると, $M \leq \dfrac{1}{2}N(N-1)=O(N^2)$ となり, 最悪時間計算量 $O(NM)=O(N^3)$ となってしまう.

解法2 (高速化)

よって, 高速化が必要になるが, 今回の問題の場合, 時間計算量を $o(N^3)$ にすることは厳しい. しかし, 例えば C++ においては bitset というデータ構造を用いることにより, $\# (N_G(x) \cap N_G(y))$ を求める過程が $64$ 倍高速化される.

よって, $X$ を求めるための計算量が

$M \times \dfrac{N}{64} \leq \dfrac{N^3}{128} \leq 2.2 \times 10^8$

となり, 実装に十分の注意を払えば実行時間制限に間に合わせることができる.