Pythonで単調増加数列から目的の要素位置を二分探索で求める方法

問題の概要

数値 l と、単調増加する数列 f(m) が与えられます。この数列は次の式で定義されます。

f(m) = am + bm・[log₂(m)] + cm³

ここで、a = 1, 2, 3, …、b = 1, 2, 3, …、c = 0, 1, 2, 3, … です。

[log₂(m)] の意味

[log₂(m)] は底が2の対数を計算し、小数点以下を切り捨てた値を表します。具体的には次のようになります。

• m = 1 のとき → 0
• m = 2〜3 のとき → 1
• m = 4〜7 のとき → 2
• m = 8〜15 のとき → 3（以降も同様）

求めるべきもの

f(m) = l を満たす m の値を見つけることが目標です。もし l が数列中に存在しない場合は 0 を出力します。なお、扱う値はすべて64ビットで表現可能であり、3つの整数 a、b、c はそれぞれ100以下であるとします。

たとえば、入力が a = 2、b = 1、c = 1、l = 12168587437017 の場合、出力は 23001 になります。これは f(23001) = 12168587437017 が成立するためです。

解法のアプローチ：二分探索

f(m) は単調増加関数であるため、二分探索（バイナリサーチ）を使うことで効率的に解けます。探索範囲の上限は、c ≥ 1 の場合は 1,000,000、c = 0 の場合は 10¹⁵ に設定します。手順は以下の通りです。

1. 関数 solve(a, b, c, n) を定義し、f(n) の値を計算して返します。
   • ans := a × n
   • lg_val := log₂(n) の小数点以下切り捨て値
   • ans := ans + b × n × lg_val
   • ans := ans + c × n³
2. メイン処理では、begin := 1、end := 探索上限、ans := 0 で初期化します。
3. begin ≤ end の間、以下を繰り返します。
   • mid := (begin + end) ÷ 2 の整数部分
   • val := solve(a, b, c, mid)
   • val が l と一致すれば、ans := mid としてループを抜けます。
   • val > l ならば、end := mid − 1 とします。
   • それ以外ならば、begin := mid + 1 とします。
4. 最後に ans を返します。

この方法により、計算量はわずか O(log N) となり、非常に大きな値でも高速に答えを得られます。

実装例

以下はPythonによる実装例です。

from math import log2, floor

SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000

def solve(a, b, c, n):
    ans = a * n
    lg_val = floor(log2(n))
    ans += b * n * lg_val
    ans += c * n**3
    return ans

def get_pos(a, b, c, k):
    begin = 1
    end = SMALLER_VAL
    if c == 0:
        end = LARGER_VAL
    ans = 0
    while begin <= end:
        mid = (begin + end) // 2
        val = solve(a, b, c, mid)
        if val == k:
            ans = mid
            break
        elif val > k:
            end = mid - 1
        else:
            begin = mid + 1
    return ans

a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))

入力

2, 1, 1, 12168587437017

出力

23001

まとめ

本記事では、単調増加する特殊な数列 f(m) = am + bm・[log₂(m)] + cm³ において、与えられた値 l に一致する要素の位置 m を二分探索で求める方法を紹介しました。単調性を活かした二分探索は線形探索よりも圧倒的に高速であり、大きな探索範囲でも実用的に動作します。同様の問題に直面した際には、ぜひこの手法を応用してみてください。