Pythonで有界配列の指定インデックスにおける最大値を二分探索で求める方法

この記事では、3つの整数 n、index、maxSum が与えられたとき、条件を満たす配列 nums の中で nums[index] の最大値を求める問題をPythonで解く方法を解説します。

問題の条件

配列 nums は以下の条件をすべて満たす必要があります。

• nums のサイズは n である
• nums のすべての要素は正の整数である
• すべての i（0 <= i < n-1）に対して |nums[i] - nums[i+1]| <= 1 が成り立つ
• nums の全要素の合計は maxSum を超えない
• nums[index] を最大化する

入力例と出力例

たとえば、n = 6、index = 3、maxSum = 8 が与えられた場合、出力は 2 になります。これは [1, 2, 2, 2, 1, 1] のような配列を作ればすべての条件を満たし、そのとき nums[3] = 2 が最大になるためです。

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

この問題は二分探索（バイナリサーチ）を使って効率的に解けます。nums[index] の候補値 mid を仮定し、その値で配列を構成したときの合計が maxSum 以内に収まるかを判定しながら、範囲を絞り込んでいきます。隣接要素の差が1以下という条件から、index の位置から左右に向かって値が1ずつ減少する山型の配列が最も効率的であることがポイントです。

アルゴリズムの手順

1. left を maxSum // n（切り捨て除算）、right を maxSum + 1 に初期化する
2. ans を 0 で初期化する
3. left < right の間、以下を繰り返す
   • mid := left + (right - left) // 2
   • ind_l := index より左側の部分に mid を頂点として配置したときの合計値
   • ind_r := index より右側の部分に mid を頂点として配置したときの合計値
   • ind_l + ind_r <= maxSum なら ans := mid とし、left := mid + 1 に更新（もっと大きい値を試せる）
   • そうでなければ right := mid に更新（値を小さくする必要がある）
4. ans を返す

Pythonでの実装例

def solve(n, index, maxSum):
   left, right = maxSum//n, maxSum+1
   ans = 0
   while(left<right):
      mid = left + (right-left)//2
      ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
      ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))

      if ind_l + ind_r <=maxSum:
         ans = mid
         left = mid+1
      else:
         right = mid
   return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

実行結果

入力：

6, 3, 8

出力：

2

計算量について

二分探索により候補値の範囲を半分ずつ絞り込むため、時間計算量は O(log(maxSum)) となります。各判定処理は定数時間で行えるため、n や maxSum が大きくなっても高速に動作します。単純な貪欲法や全探索では間に合わない大きな制約でも対応できるのがこの手法の利点です。