Kazun の競プロ記録

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

AtCoder Beginner Contest 226 D 問題 Teleportation

AtCoder ABC ABC226 D問題 400 pts

問題

提出解答

問題の概要

以下を満たす $\mathbb{Z}^2$ の部分集合 $S$ で, 濃度の最小値を求めよ.

任意の $1 \leq i,j \leq N, i \neq j$ に対して, $(x_j-x_i, y_j-y_i)=(ka,kb)$ となる $(a,b) \in S$ と, 正の整数 $k \gt 0$ が存在する.

制約

$1 \leq N \leq 500$
$0 \leq x_i,y_i \leq 10^9$
$i \neq j \Rightarrow (x_i,y_i) \neq (x_j,y_j)$

解法

$(a,b) \in \mathbb{Z}^2$ に対して, $T(a,b):=\{(i,j) \mid \exists k \gt 0 {\rm ~s.t.~} (x_j-x_i,y_j-y_i)=(ka,kb) \}$ とする. このとき, 正の整数 $k$ に対して, $T(ka,kb) \subset T(a,b)$ である. このことから, 以下のことがわかる.

$(a,b) \in S$ で, $a,b$ が公約数 $d$ を持つならば, $(a,b) \in S$ を $(a/d, b/d) \in S$ に置き換えてもよい.

また, この議論をできるだけ行うと, 以下のように帰着できる.

$(a,b) \in S$ で, $a,b$ の最大公約数を $g (\gt 0)$ としたとき, $(a,b) \in S$ を $(a/g, b/g) \in S$ に置き換えてもよい.

よって, $S$ の元は符号付きで, 互いに素であるとしてもよい.

逆に, $(a,b), (a',b') \in S$ で, $a$ と $b$ , $a'$ と $b'$ が互いに素のとき, $T(a,b) \cap T(a',b') =\emptyset$ であり, 互いに素であるような $(a,b)$ は他の互いに素であるような $\mathbb{Z}^2$ の組で代替がないことになる.

以上のことから, 以下のようにして求めることができる.

$S$ を空集合とする.
なる全ての組に対して, 以下を実行する.
1. $a_{i,j}:=x_j-x_i, b_{i,j}:=y_j-y_i$ とし, $g_{i,j}:=\operatorname{gcd}(a_{i,j}, b_{i,j})$ とする.
2. $(a_{i,j}/g_{i.j}, b_{i,j}/g_{i,j})$ を $S$ に加える.
$|S|$ が答え.

$\operatorname{gcd}(p,q)$ を求めるための計算量は, $O(\log \max(p,q))$ だったので, このアルゴリズムにより, 計算量 $O(N^2 \log \max(X,Y))$ で求めることができる.