概要

長さ \(L\) のロープを半分に折りたたむ操作（切り上げ除算）を繰り返し、長さ \(W\) 以下にするために必要な最小回数を求める問題です。

考察

問題の整理

ロープの長さが \(x\) のとき、1回折りたたむと長さは \(\lceil x/2 \rceil\) になります。これを繰り返して \(W\) 以下にしたいです。

具体例: \(L = 11\), \(W = 3\) の場合

回数	長さ
0回	11
1回	\(\lceil 11/2 \rceil = 6\)
2回	\(\lceil 6/2 \rceil = 3\)

2回で \(W = 3\) 以下になるので、答えは 2 です。

素朴なアプローチで問題ないか？

一見すると \(L\) が最大 \(10^{18}\) なので心配になりますが、1回の操作で長さがおよそ半分になるため、ループ回数は最大でも \(\log_2(10^{18}) \approx 60\) 回程度です。これは十分高速なので、単純にシミュレーションするだけで解けます。

切り上げ除算の実現

\(\lceil x/2 \rceil\) を整数演算で計算するには、\((x + 1) \div 2\)（切り捨て除算）を使います。

• \(x = 11\)（奇数）: \((11 + 1) / 2 = 6\) ✓（\(\lceil 11/2 \rceil = 6\)）
• \(x = 6\)（偶数）: \((6 + 1) / 2 = 3\) ✓（\(\lceil 6/2 \rceil = 3\)）

一般に、整数 \(x\) を整数 \(d\) で割った切り上げは \(\lceil x/d \rceil = \lfloor (x + d - 1) / d \rfloor\) で求められます。\(d = 2\) のとき \((x + 1) // 2\) となります。

アルゴリズム

1. カウンタ count を \(0\) に初期化する。
2. \(L > W\) である間、以下を繰り返す：
   • \(L\) を \(\lceil L/2 \rceil = (L + 1) // 2\) に更新する。
   • count を \(1\) 増やす。
3. count を出力する。

L, W = map(int, input().split())
count = 0
while L > W:
    L = (L + 1) // 2
    count += 1
print(count)

計算量

• 時間計算量: \(O(\log L)\)（毎回長さがおよそ半分になるため、ループは最大約 \(60\) 回）
• 空間計算量: \(O(1)\)

実装のポイント

• 切り上げ除算の書き方: (L + 1) // 2 で \(\lceil L/2 \rceil\) を正しく計算できます。Python では // が切り捨て除算（正の数に対して）なので、分子に \(d - 1 = 1\) を足すテクニックが使えます。

• 最初から条件を満たす場合: \(L \leq W\) のとき while ループに入らず、count = 0 がそのまま出力されるため、特別な場合分けは不要です。

• 多倍長整数: \(L\) が最大 \(10^{18}\) ですが、Python は整数のオーバーフローがないため、そのまま扱えます。C++ などを使う場合は long long 型を使う必要があります。

  ソースコード

L, W = map(int, input().split())
count = 0
while L > W:
    L = (L + 1) // 2
    count += 1
print(count)

---

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