概要

細胞を \(S\) 個から \(T\) 個にするために必要な「分裂促進」操作（細胞数を2倍にする操作）の最小回数を求める問題です。操作回数が \(K\) 回以内で達成可能かどうかを判定します。

考察

重要な気づき

1. 操作の性質を理解する

   • 1回の操作で細胞数は2倍になる
   • \(n\) 回操作すると、細胞数は \(S \times 2^n\) 個になる

2. \(T\) に到達できる条件

   • \(T = S \times 2^n\) となる非負整数 \(n\) が存在する必要がある
   • これは「\(T\) が \(S\) の倍数」かつ「\(T / S\) が2のべき乗」であることと同値

3. 具体例で確認

   • \(S = 3, T = 12\) の場合：\(12 / 3 = 4 = 2^2\) なので、2回の操作で達成可能
   • \(S = 3, T = 9\) の場合：\(9 / 3 = 3\) は2のべき乗ではないので、達成不可能
   • \(S = 5, T = 7\) の場合：\(7\) は \(5\) の倍数ではないので、達成不可能

素朴なアプローチの問題点

単純に \(S\) を2倍していって \(T\) に到達するかを確認する方法も考えられますが、\(K\) が最大100なので \(2^{100}\) は非常に大きな数になります。しかし、この問題では \(K \leq 100\) であり、ループは最大100回程度で済むため、この方法でも問題ありません。

今回の解法では、\(T / S\) が2のべき乗かどうかを直接判定するアプローチを採用しています。

アルゴリズム

1. \(T\) が \(S\) で割り切れるか確認

   • 割り切れなければ -1 を出力

2. 比率 \(\text{ratio} = T / S\) を計算

3. \(\text{ratio}\) が2のべき乗かどうか判定

   • \(\text{ratio}\) を2で割り続ける
   • 途中で奇数（1以外）が現れたら2のべき乗ではない → -1
   • 最終的に1になれば2のべき乗

4. 必要な操作回数を確認

   • 2で割った回数が必要な操作回数 \(n\)
   • \(n \leq K\) なら \(n\) を出力、そうでなければ -1

具体例のトレース

\(S = 4, T = 32, K = 5\) の場合： - \(32 \mod 4 = 0\) ✓ - \(\text{ratio} = 32 / 4 = 8\) - \(8 \to 4 \to 2 \to 1\)（3回割った） - 3回の操作が必要、\(3 \leq 5\) なので答えは 3

計算量

• 時間計算量: \(O(\log(T/S))\)
  • \(\text{ratio}\) を2で割る操作は、\(\text{ratio}\) の2進数表現のビット数に比例
  • 最大でも約60回程度（\(T/S \leq 10^{18}\) のため）
• 空間計算量: \(O(1)\)
  • 変数をいくつか保持するだけ

実装のポイント

• 整数オーバーフローに注意: \(S, T\) が最大 \(10^{18}\) まであるが、Pythonでは整数のオーバーフローを気にする必要がない

• \(T = S\) の場合: \(\text{ratio} = 1 = 2^0\) なので、0回の操作で達成可能（正しく処理される）

• 2のべき乗判定: temp % 2 != 0 で奇数かどうかを判定し、2のべき乗でない場合を検出

  ソースコード

def solve():
    S, T, K = map(int, input().split())
    
    # T must be a multiple of S for it to be reachable
    if T % S != 0:
        print(-1)
        return
    
    ratio = T // S
    
    # ratio must be a power of 2
    # Check if ratio is a power of 2
    if ratio == 0:
        print(-1)
        return
    
    # Count how many times we need to multiply by 2
    # ratio must be 2^k for some k >= 0
    count = 0
    temp = ratio
    while temp > 1:
        if temp % 2 != 0:
            # Not a power of 2
            print(-1)
            return
        temp //= 2
        count += 1
    
    # Now count is the number of operations needed
    if count <= K:
        print(count)
    else:
        print(-1)

solve()

この解説は claude4.5opus によって生成されました。