概要

長さ \(L\) センチメートルのロープを、「長さを半分（端数切り上げ）にする」という操作を繰り返して \(W\) センチメートル以下にするために必要な最小の操作回数を求める問題です。

考察

この問題のポイントは、「操作を1回行うごとにロープの長さが指数関数的に減少していく」という点です。

1. 操作のシミュレーション

現在のロープの長さを \(x\) とすると、1回折りたたんだ後の長さは \(\lceil x / 2 \rceil\) となります。 例えば、 \(L=10, W=2\) の場合を考えてみましょう。 - 0回目：10cm - 1回目：\(\lceil 10 / 2 \rceil = 5\)cm（まだ \(W\) より大きい） - 2回目：\(\lceil 5 / 2 \rceil = 3\)cm（まだ \(W\) より大きい） - 3回目：\(\lceil 3 / 2 \rceil = 2\)cm（\(W\) 以下になった！） したがって、答えは 3回 となります。

2. 制約と計算量

ロープの長さ \(L\) は最大で \(10^{18}\) と非常に大きな値ですが、1回の操作で長さは約半分になります。 \(2^{60}\) は \(10^{18}\) を超えるため、どのような入力であっても高々 60回 程度の操作で \(L\) は 1 に到達します。そのため、愚直に 1回ずつ操作をシミュレーションしても十分に間に合います。

3. 切り上げの計算方法

プログラミングにおける整数除算（多くの言語で / や //）は一般的に切り捨てが行われます。 正の整数 \(x\) を 2 で割った時の切り上げ \(\lceil x / 2 \rceil\) を整数演算だけで行うには、以下の式が便利です。 - (x + 1) // 2

アルゴリズム

以下の手順で解を求めます。

1. 入力 \(L, W\) を受け取る。
2. 折りたたんだ回数を記録する変数 count を 0 で初期化する。
3. \(L > W\) である間、以下の処理を繰り返す（while 文）：
   • \(L\) を \((L + 1) // 2\) に更新する。
   • count を 1 増やす。
4. 最終的な count の値を出力する。

最初から \(L \leq W\) の場合は、while 文の条件を満たさないため count は 0 のままとなり、問題文の指示通り正しく動作します。

計算量

• 時間計算量: \(O(\log L)\) 各操作で \(L\) が半分になるため、ループの回数は \(L\) の対数に比例します。\(L=10^{18}\) のとき、ループ回数は最大でも 60回程度です。
• 空間計算量: \(O(1)\) 入力値とカウント用の変数のみを保持するため、一定のメモリ量で動作します。

実装のポイント

• 大きな数の扱い: Pythonでは標準で大きな整数（多倍長整数）を扱えるため、\(10^{18}\) という大きな値もそのまま計算できます。

• ループの条件: 「\(W\) 以下になるまで」繰り返すため、継続条件は L > W となります。

  ソースコード

import sys

def solve():
    # 入力を読み込む
    line = sys.stdin.readline()
    if not line:
        return
    L, W = map(int, line.split())

    count = 0
    # ロープの長さ L が W を超えている間、折りたたみを繰り返す
    while L > W:
        # L / 2 の切り上げを計算する
        L = (L + 1) // 2
        count += 1
    
    # 結果を出力
    print(count)

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。