D - 細胞分裂 / Cell Division 解説 by admin 印刷ページ
GPT 5.4 High概要
各細胞はほかの細胞と独立に処理できるので、まず「活性値 \(a\) の細胞 1 個をすべて \(1\) にするには何回かかるか」を考えます。
すると答えは \(a\) の素因数の「取り出す順番」だけで決まり、最小は小さい素数から、最大は大きい素数から取り出せばよいです。
考察
1. 初期の各細胞は独立
ある細胞に対する操作は、その細胞から生まれた子孫の細胞にしか影響しません。
別の初期細胞から生まれた細胞とは一切干渉しないので、
- 各 \(A_i\) について必要操作回数の最小値・最大値を求める
- それらを全部足す
で全体の答えになります。
2. 1 個の細胞だけを見る
活性値 \(x\) の細胞に対して、素因数 \(p\) を選ぶと
- \(x\) を 1 個消す
- 代わりに \(x/p\) の細胞を \(p\) 個作る
という操作になります。
たとえば \(12\) に対して \(p=2\) を選ぶと
- \(12 \to 6,6\)
です。
さらにそれぞれの \(6\) にまた操作していきます。
3. 操作回数は「素因数を取り出す順番」で決まる
\(a\) の素因数を重複込みで
\[ a = q_1 q_2 \cdots q_k \]
とします。
ここで「最初に \(q_1\) を選び、次に各子細胞で \(q_2\) を選び、……」という順番で進めると、
- 1 回目の操作：最初の細胞 1 個に対して行うので \(1\) 回
- 2 回目の段階：細胞が \(q_1\) 個あるので \(q_1\) 回
- 3 回目の段階：細胞が \(q_1 q_2\) 個あるので \(q_1 q_2\) 回
- …
- 最後の段階：\(q_1 q_2 \cdots q_{k-1}\) 回
したがって総操作回数は
\[ 1 + q_1 + q_1 q_2 + \cdots + q_1 q_2 \cdots q_{k-1} \]
になります。
4. 最小は昇順、最大は降順
では、素因数をどの順番で並べればこの和が最小/最大になるでしょうか。
隣り合う 2 つの素因数 \(a \le b\) を考え、残りの後ろ部分を固定します。
この 2 つの順番だけを比べると、
- \(a,b\) の順に置いたとき
- \(b,a\) の順に置いたとき
の差は、実は「前に大きい数を置くと、その後ろの項すべてに効いてしまう」ため、常に
\[ (a,b) の方が (b,a) より小さい \]
となります。
もう少し式で書くと、前にある素因数の積を \(P\)、後ろ部分の寄与を \(U\) とすると、
- \(a,b\) の順：\(P(1 + a + abU)\)
- \(b,a\) の順：\(P(1 + b + abU)\)
なので差は
\[ P[(1+b+abU)-(1+a+abU)] = P(b-a) \ge 0 \]
です。
つまり 小さい素因数を前に出すほど小さくなる ので、
- 最小値：素因数を 昇順
- 最大値：素因数を 降順
に並べればよいです。
5. 具体例
\(a=12=2 \times 2 \times 3\) を考えます。
- 最小：\(2,2,3\) の順
$\( 1+2+2\cdot2=1+2+4=7 \)$ - 最大：\(3,2,2\) の順
$\( 1+3+3\cdot2=1+3+6=10 \)$
実際、
最小の流れ
\(12 \to 6,6\)
\(6,6 \to 3,3,3,3\)
\(3,3,3,3 \to 1\) たち
で合計 \(7\) 回最大の流れ
\(12 \to 4,4,4\)
\(4,4,4 \to 2\) たち
\(2\) たち \(\to 1\) たち
で合計 \(10\) 回
となります。
6. 素朴な方法がだめな理由
素朴に
- 実際に細胞をシミュレーションする
- すべての選び方を探索する
と、細胞数がどんどん増えるうえ、選択肢も多くて到底間に合いません。
また、各 \(A_i\) を毎回試し割りで素因数分解すると、\(N\) が最大 \(2\times10^5\) なので重くなります。
そこで、あらかじめ 最小素因数表 (SPF) を作っておくと、高速に素因数分解できます。
アルゴリズム
- \(M=\max(A_i)\) とする。
- \(1\) から \(M\) までの 最小素因数
spfをエラトステネス風に前計算する。 - 各 \(A_i\) について以下を行う。
spfを使って素因数を重複込みで列挙する。
この実装では自然に昇順で得られる。- 最小値を計算する。
昇順の素因数列を \(p_1,p_2,\dots,p_k\) とすると $\( 1 + p_1 + p_1p_2 + \cdots + p_1p_2\cdots p_{k-1} \)$ を求める。 - 最大値を計算する。
同じ素因数列を逆順にして、同様に $\( 1 + q_1 + q_1q_2 + \cdots + q_1q_2\cdots q_{k-1} \)$ を求める。
- それぞれ全 \(A_i\) 分を足して出力する。
同じ値が何度も出る場合に備えて、memo で結果を再利用しています。
計算量
- 時間計算量: \(O(M \log \log M + N \log M)\)
ただし \(M=\max(A_i)\)
（素因数分解 1 回あたりの回数は、割るたびに少なくとも \(2\) で割れるので高々 \(O(\log M)\)） - 空間計算量: \(O(M + N)\)
実装のポイント
spf[x]を使えば、xを高速に素因数分解できます。- 素因数列から答えを作るときは、
prod = 1として- 現在の
prodを答えに足す prod *= p
- 現在の
を順に繰り返せば $\( 1,\ p_1,\ p_1p_2,\ \dots \)\( を自然に作れます。 - \)A_i=1\( のときは操作不要なので \)(0,0)$ です。 - 合計値は大きくなりうるので、他言語なら 64bit 整数が必要です。
ソースコード
import sys
from math import isqrt
def build_spf(n: int):
spf = [0] * (n + 1)
if n >= 2:
for i in range(2, n + 1, 2):
spf[i] = 2
r = isqrt(n)
for i in range(3, n + 1, 2):
if spf[i] == 0:
spf[i] = i
if i <= r:
step = i << 1
start = i * i
for j in range(start, n + 1, step):
if spf[j] == 0:
spf[j] = i
return spf
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
n = data[0]
A = data[1:1 + n]
m = max(A) if A else 1
spf = build_spf(m)
memo = {1: (0, 0)}
total_min = 0
total_max = 0
for a in A:
res = memo.get(a)
if res is None:
x = a
facs = []
while x > 1:
p = spf[x]
facs.append(p)
x //= p
prod = 1
mn = 0
for p in facs:
mn += prod
prod *= p
prod = 1
mx = 0
for p in reversed(facs):
mx += prod
prod *= p
res = (mn, mx)
memo[a] = res
total_min += res[0]
total_max += res[1]
print(total_min, total_max)
if __name__ == "__main__":
main()
この解説は gpt-5.4-high によって生成されました。
投稿日時:
最終更新: