Pythonでk回の操作後に実現可能な最小の最大値を求めるプログラム

数値のリスト nums と整数 k が与えられたとします。ここで考える「操作」とは、リスト内の任意の要素から 1 を引くことです。この操作は合計 k 回まで実行できます。目標は、k 回の操作を行った後のリストにおいて、最大値が取り得る最小の値を求めることです。

たとえば、入力が nums = [3, 4, 6, 5]、k = 6 の場合、出力は 3 になります。これは、4 を 1 回、6 を 3 回、5 を 2 回減らすことで、リスト全体を [3, 3, 3, 3] にできるためです。

解法の考え方

この問題は貪欲法（グリーディ法）で効率的に解くことができます。基本の発想は、「現在の最大値と同じ値を持つ要素をすべてまとめて 1 ずつ減らし、残りの操作回数が足りなくなった時点で、その時点の最大値を答えとして返す」というものです。

アルゴリズムの手順

• 数値を降順にソートする
• i := 0 と初期化する
• curr := nums[0]（現在の最大値）とする
• k > 0 の間、以下を繰り返す：
  • i がリストのサイズ未満 かつ nums[i] == curr である間、i := i + 1 を繰り返す（現在の最大値と同じ値を持つ要素の個数を数える）
  • k >= i ならば：
    • k := k - i
    • curr := curr - 1
  • それ以外の場合：
    • curr を返す
• curr を返す

この方法では、最大値のレベルを 1 段ずつ下げながら、そのレベルに属する全要素を同時に減らしていくため、限られた操作回数を無駄なく使えます。

実装例

以下の実装を見ると、動作の流れがよりよく分かります：

class Solution:
    def solve(self, nums, k):
        nums.sort(reverse=True)
        i = 0
        curr = nums[0]
        while k > 0:
            while i < len(nums) and nums[i] == curr:
                i += 1
            if k >= i:
                k -= i
                curr -= 1
            else:
                return curr
        return curr

ob = Solution()
nums = [3, 4, 6, 5]
k = 6
print(ob.solve(nums, k))

入力

[3, 4, 6, 5], 6

出力

3

計算量

ソートに O(n log n) かかり、その後の処理はポインタ i が各要素を高々 1 度しか通過しないため O(n) です。したがって全体の計算量は O(n log n) となります。要素を 1 つずつ個別に操作をシミュレートする素朴な手法と比べて、はるかに効率的です。