E1 - Make K [Easy]

概要

基礎的な DP と，高速化の工夫を問う問題です．
柔らに考えると案外簡単な問題かもしれません．

問題特有の性質と，計算量の見積もりに注意してください．

問題原案：tnodino

略解

$1$ 次元の DP を考えます．BFS 等でもよいです．
事前に全ての値について答えを求めることができるので，各クエリには定数時間で答えられます．

以降前計算について，($K$ はとり得る最大の値としてよいです．)
[Easy] は愚直に約数の総和を計算すれば $O(K \sqrt K)$ 時間で解けます．
[Hard] に正解するためには，約数の総和の求め方を工夫する必要があります．$O(K \log K)$ 時間程度を許容します．

解説

$Ⅰ.$ 操作が満たす性質

正の整数 $k$ の正の約数の総和を $S_k$ とします．

ある正の整数 $k$ に対して，$k$ は自身の正の約数として $1$ および $k$ 自身を持ちますから，明らかに $\forall_{k\geq2}\;k < k+1 \leq S_k$ といえます．

つまり，$\text A, \text B$ いずれの値を選んで操作を行っても，$x$ の値は減少しません．
($1$ に関して $\text B$ の操作を行ったときに限って $S_1 = 1$ より変化しませんが，操作の「最小回数」を知ることが目的なので，$x = 1$ のときは常に $\text A$ を選ぶこととして問題ありません．)

$Ⅱ.$ 動的計画法

(動的計画法(DP)についての詳しい解説は他サイト様へ委ねます．よろしければ TGC000-G も参照ください．)

次のような DP を考えます．
ここで，$K$ はとり得る最大の値とすることで，全てのクエリに対しての答えを求めたことになります．

定義

• $\mathrm {DP}[k] \coloneqq ( x$ を $k$ に等しくするために必要な操作回数の最小値$)$

初期状態

• $\mathrm {DP}[1] = 0$
• $\mathrm {DP}[i] = \infty \hspace{0.3em} \scriptsize (2 \leq i \leq K)$

遷移

• $\text{For}\;k \xleftarrow{\text{each}} [1, 2, \ldots, K):$
  • $\mathrm {DP}[k + 1] \xleftarrow{\min} \mathrm {DP}[k] + 1 \>(\mathrm{A}$ の値を選ぶ場合$)$
  • $\mathrm {DP}[S_k] \xleftarrow{\min} \mathrm {DP}[k] + 1 \>\>\>\>\>\,\, (\mathrm{B}$ の値を選ぶ場合$)$

「実装例」の項も参照してください．

$Ⅲ.$ $S_k$ の算出

愚直に求める (TLE)

$1 \leq v \leq k$ を満たす $v$ を全探索し，$v$ が $k$ の約数ならば $S_k$ に $v$ を加算することで求められます．
この方法の時間計算量は $O(k)$ ですから，DP の遷移も含めると，$O(K^2)$ 時間となって，[Easy] の制約下でも間に合いません．

少し工夫する ([Easy] に正解)

ある正の整数 $v$ について，$v$ が $k$ の約数ならば，$\frac{k}{v}$ も同時に $k$ の約数となります．
つまり，探索する $v$ は $1\ \leq v \leq \sqrt k$ を満たすもののみで十分とわかります．

C++ による実装例を次に示します．

$\\$
もう少し工夫する ([Hard] に正解)

先述した方法は「$1 \leq k \leq K$ を満たすすべての $k$ について，$1 \leq v \leq \sqrt k$ を満たす $v$ を全探索し，$v$ が $k$ の約数ならば $S_k$ に $v$ と $\frac{k}{v}$ とを加算する」というものでした．
探索対象となる $v$ の中には $k$ の約数でないものも含まれるため，無駄がありそうです．
逆に，「必ず何かの約数となる」ような値を列挙できれば，かなり効率的であると考えられます．

少し視点を変えて「$1 \leq k \leq K$ を満たす $k$ の倍数 $m \in V_k \coloneqq \{\, ik\,|\,k \leq ik \leq K \,\}$ それぞれについて，$S_m$ に $k$ を加算する」という方法を考えてみましょう．
実際に，この方法でもすべての $1 \leq k \leq K$ を満たす $k$ について，正の約数の総和を列挙できることが分かります．

「$k$ の約数を列挙する」代わりに「$k$ が約数となる $m \, (\leq K)$ を列挙する」といったイメージです．
直感的には後者の方が無駄がなく効率がよさそうですね．

これをより確実に評価してみましょう．

$|V_k| = \lfloor \frac{K-k}{k} \rfloor = \lfloor \frac{K}{k} \rfloor - 1$ となり，$V_k$ の要素は $O(|V_k|)$ 時間で列挙できますから，$1 \leq k \leq K$ を満たすすべての $k$ について $V_k$ の要素を列挙しようとすると $\displaystyle \sum_{1 \leq k \leq K} \Big( \lfloor \frac{K}{k} \rfloor - 1 \Big) \backsimeq K \sum_{1 \leq k \leq K} \frac{1}{k} \backsimeq K \log K$ 回程度の計算が必要になります．

しかしこれならば [Hard] の制約 $K \leq 2\times 10^6$ のもとでも十分に間に合います．

なお，調和数🔗が対数程度の速度で発散するという事実を知らなくても，(プログラムや電卓を用いて)以上の(総和を用いた方の)式へ実際に $K = 2 \times 10^6$ を代入して計算してみることでも 確かに間に合いそうだ ということが確かめられるはずです．

$Ⅳ.$ 発展

$1)$ 類題

• EDPC $\hspace{0.15em}$ A - Frog 1
• 第二回日本最強プログラマー学生選手権 $\hspace{0.15em}$ C - Max GCD 2
• ABC 254 $\hspace{0.15em}$ B - Practical Computing
• ABC 240 $\hspace{0.15em}$ C - Jumping Takahashi
• ABC 264 $\hspace{0.15em}$ D - "redocta".swap(i,i+1)
• ABC 242 $\hspace{0.15em}$ C - 1111gal password
• ARC 135 $\hspace{0.15em}$ A - Floor, Ceil - Decomposition
• ABC 220 $\hspace{0.15em}$ D - FG operation
• ABC 178 $\hspace{0.15em}$ D - Redistribution
• ABC 253 $\hspace{0.15em}$ E - Distance Sequence
• ABC 272 $\hspace{0.15em}$ E - Add and Mex

実装例

$S_k$ の値は DP の遷移の前に計算してもよいですが，DP を更新しながら同時に計算していくこともできます．
こちらの方が実装が少々楽です．

$\\$

余談

調和数... どこか見覚えがありますね

ええ．まさか被るとは思いませんでした．(ABC272-E)
で，でも．この問題の原案が出たのは 8/19 時点なのでわざとじゃないですよ...？？(

許してね☆