Kazun の競プロ記録

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

AtCoder Beginner Contest 276 D問題 Divide by 2 or 3

AtCoder ABC276 ABC D問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の正の整数列 $A=(A_1, \dots, A_N)$ が与えられる.

次の操作を $0$ 回以上行い, $A_1=\dots=A_N$ にすることは可能か? 可能ならば操作回数の最小値を求めよ.

$A_i$ が $2$ の倍数であるような $1$ 以上 $N$ 以下の整数 $i$ を選び, $A_i$ を $A_i/2$ に置き換える.
$A_i$ が $3$ の倍数であるような $1$ 以上 $N$ 以下の整数 $i$ を選び, $A_i$ を $A_i/3$ に置き換える.

制約

$2 \leq N \leq 1000$
$1 \leq A_i \leq 10^9$

解法

操作は可換であるので, 各項において, $2,3$ をそれぞれ何回割るかに着目すれば良い.

$p=2,3$ と正の整数 $n$ において, $\nu_p(n)$ で $n$ を $p$ で割り切れる最大回数と定義する.

このとき, 正の整数 $n$ が操作によって操作 $m$ にすることが可能であることの必要十分条件は $n=m \times 2^x \times 3^y$ となるような非負整数が存在することであり, 操作回数は $(x+y)$ 回である.

また, 非負整数 $x,y$ に対して, $n=m \times 2^x \times 3^y$ となる整数 $m$ が存在することと, $0 \leq x \leq \nu_2(n), 0 \leq y \leq \nu_3(n)$ であることが同値である.

よって, $i=1,2, \dot,s N$ に対して正の整数からなる集合 $S_i$ を

$S_i=\left\{\dfrac{A_i}{2^x 3^y} \middle| 0 \leq x \leq \nu_2(A_i), 0 \leq y \leq \nu_3(A_i) \right\}$

とする. このとき, 操作によって全ての項が等しくすることが可能であることと,

$\displaystyle S:=\bigcap_{i=1}^N S_i \neq \emptyset$

であることが同値である.

よって, $S$ が空集合であれば不可能である.

$S$ が空集合ではないとする. このとき, 解答は

$\displaystyle \min_{x \in S} \sum_{i=1}^N \left(\nu_2 \left(\dfrac{A_i}{x} \right)+ \nu_3 \left(\dfrac{A_i}{x} \right) \right)$

である.

計算量については $S_i$ を求めるパートがボトルネックで各 $S_i$ に対して $O( (\log A_i)^2)$ 時間であるから, 全体では $O(N (\log \max A)^2)$ 時間である.

なお, 素因数分解を利用して考察を進めることにより, $O(N \log \max A)$ 時間で求めることもできる.