[Python] 二分探索の応用問題: 最大値の探索

アルゴリズムとデータ構造
記事内に広告が含まれています。
スポンサーリンク

本記事では、二分探索の応用問題である『値の最大化問題』ついて解法をまとめます。

スポンサーリンク

問題の考え方: コピペ用コード

問題に慣れるまでは、以下の二点に集中すると考えやすいと思います。

  • 3行目の条件判定の関数
  • 13-16行目の範囲の絞り込み

#1. 条件を満たすか判定する関数
def condition(*arg):
    #問題文にあう条件を判定

#2. 二分探索パート
left, right = 0, MAX #下限値、上限値

#解の範囲が十分小さくなるまで繰り返す
for i in range(100):
    mid = (right+left)/2  #中間値
    if condition(*arg):
        left = mid #もしくは、right = mid
    else:
        right = mid #もしくは、left = mid

この二箇所をどうするか考える方針で話を進めていきます。

また、pythonの標準ライブラリに bisect がありますが、本記事では扱いません。

bisect の具体的な使い方に関しては、以下の記事などをご参照ください。

値の最大化問題 1

以下の問題を二分探索で解いてみます。

アルル は $N$本のひもを持っています。
ひもには 0 から $N-1$ までの番号がついており、ひも $i$の長さは $L_i$です。

アルルは、これらのひもを切って同じ長さのひもを $K$ 本用意しようと考えています。
アルルが用意できるひもの長さの最大値を求めてください。
ただし、ひも同士を連結させることはできません。

答えを出力してください。絶対誤差 (想定解と出力の差の絶対値) は $10^{-6}$ まで許されます。

アルゴ式 Q2-8.ひもを切る

問題の趣旨について

用意できるひもの長さの最大値 $X’$ と仮定します。その時、$X’$以上では本数が $K$ 本未満になり、$X’$ 以下では $K$本以上になることが言えます。

図にすると以下のように書けます。

図1: この問題の趣旨について.
ある値$X’$が存在し、この値を境界に条件を満たす/満たさないが変わります。この$X’$を見つけることがこの問題の課題です。

この$X’$を見つけることが問題の要求です。言い換えると、『条件を満たす最大値』の探索と解釈できます。

判定関数について

切り取ったひもの長さを $X$ と仮定します。ひも $l_i$ からは $\lfloor l_i/X \rfloor$ 本切り取ることができます。

そのため、問題文の要求は以下のように定式化できます。

$$\sum_{i=0}^{N-1} \lfloor l_i/X \rfloor >=K \tag{eq. 1}$$

この式を満たすかどうかの判定関数をコーディングできればokです。

補足ですが、$\lfloor x \rfloor$は小数部分の切り捨てを意味します。例えば、$\lfloor 3.14 \rfloor = 3$ です。

範囲の絞り込みについて

$$\sum_{i=0}^{N-1} \lfloor l_i/X \rfloor >=K $$

この数式を満たす場合を考えます。その場合、$X$はさらに大きい値も取り得るため、大きい方の範囲に絞り込むことが可能です。すなわち、 left = mid と絞り込めます。

図2: (eq1.)を満たす場合の概念図. 赤矢印の部分だけ値を大きくできるため、下限値 left を大きくできます.

逆に、この式を満たさない場合、$X$ が大きすぎることを意味します。そのため、 right=mid と絞り込み、小さい範囲で値を探索します。

図3: (eq.1)を満たさない場合. 青矢印の分だけ小さくする余地があるため、上限値を小さくできます.

Pythonの解答コード

N,K = map(int, input().split())
L = list(map(int, input().split()))

#1. 条件を満たすか判定する関数
def Condition(X,K):
    ans = 0
    for li in L:
        ans += int(li/X)
    #条件:K以上か否か
    if ans >= K:
        return True
    else:
        return False

#2. 二分探索パート
left, right = 0, 10**5+1
#解の範囲が十分小さくなるまで繰り返す
while right - left > 1e-8:
    mid = (left + right)/2
    
    if Condition(mid, K):
        #Xをより長くできる可能性があるため、下限値を上げる
        left = mid
    else:
        #Xが長すぎるため、上限値を小さくして探索範囲を狭める
        right = mid
    
    

print(left)

上記のコードで アルゴ式 Q2-8.ひもを切る をACすることができました。

値の最大化問題 2

AtCoder Beginner Contest 146 C の問題です。

高橋くんは整数を 1 つ買いに整数屋さんに行きました。

整数屋さんには 1 以上 $10^9$ 以下の整数が売られていて、整数 $N$ を買うためには $A\times N + B\times d(N)$ が必要です。ここで、$d(N)$ は $N$ の十進表記での桁数です。

高橋くんの所持金が $X$ 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0 を出力してください。

AtCoder Beginner Contest 146 C- Buy an Integer

購入できる整数の最大値を探索する問題です。

判定関数について

整数$N$の金額と所持金$X$について、

$$ A\times N + B\times d(N) <= X$$

この式を満たすかどうかの判定関数をコーディングできればokです。

Pythonの解答コード

A,B,X = map(int, input().split())

def condition(a,b,n):
    digits = len(str(n))
    return a*n +b*digits <= X

left, right = 0, 10**(9)+1
for i in range(100): #while right - left > 1: としてもok
    mid = int( (right + left)/2 )
    if condition(A, B, mid):
        #midよりたくさん買える可能性がある
        left = mid
    else:
        #midが高すぎるため低くする
        right = mid

print(left)

ちなみに、答えの最大値が$10^9$ のため、最悪でも$\mathrm{log_2}(10^9) \sim 30$ 回の繰り返しで答えに辿り着きます。したがって、for文 の100回ループは十分と言えます。

上記のコードで AtCoder Beginner Contest 146 C- Buy an Integer でACできたことを確認済みです。

まとめと参考

二分探索の応用問題の考え方と実装コード例についてまとめました。

慣れるまでは、コピペ用コードの1.判定関数 と 2.範囲の絞り込み を集中的に考えると理解しやすいと思います。

他にも問題があると思うので、適宜追加していきたいと思います。

プログラミングコンテストチャレンジブック [第2版]|マイナビブックス
ひもを切る | アルゴ式(beta)
C - Buy an Integer
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.