Pythonで配列の減少・再配置後に取得できる最大要素を求める方法

問題概要

配列 arr が与えられたとします。この配列に対していくつかの操作を行い、次の条件を満たすようにする必要があります。

• arr の最初の要素は必ず 1 であること。

• 隣接する任意の 2 つの要素の絶対差が 1 以内であること。

使用できる操作は次の 2 種類で、それぞれ何度でも実行できます。

• arr 内の任意の値を、それより小さい正の整数へ減らす。

• arr の要素を任意の順序に並べ替える。

これらの操作を実行して上記の条件を満たしたとき、arr 内に残せる最大の値を求めるのが目的です。

入力例

たとえば arr = [3,3,2,3,2] の場合、出力は 3 になります。これは、最後の要素を 1 に減らし、その後 [1,2,3,3,3] のように並べ替えることで条件を満たせるためです。このときの最大値は 3 となります。

解法アプローチ

この問題は、以下の手順で解くことができます。

1. リスト arr を昇順にソートする。
2. arr[0] を 1 に設定する。
3. i を 1 から配列の長さ − 1 までループさせ、各要素に対して arr[i] = min(arr[i-1] + 1, arr[i]) を適用する。
4. 最後に arr の最大値を返す。

このアルゴリズムのポイントは、まず配列をソートすることで、小さい値から順に制約を確認できる点にあります。先頭を 1 に固定した後、「前の要素 + 1」と元の値のうち小さい方を各要素に代入していくことで、隣接要素間の差が 1 以内になるように制御します。これにより、各位置で可能な限り大きな値を維持しながら条件を満たすことができます。

実装例

理解を深めるために、以下の Python コードをご覧ください。

def solve(arr):
   arr.sort()
   arr[0] = 1

   for i in range(1, len(arr)):
      arr[i] = min(arr[i - 1] + 1, arr[i])

   return max(arr)

arr = [3,3,2,3,2]
print(solve(arr))

入力

[3,3,2,3,2]

出力

3

計算量について

この解法の時間計算量は O(n log n) であり、その大部分はソート処理によるものです。ソート後の線形走査は O(n) で完了します。また、入力配列をそのまま書き換えるインプレース処理のため、追加の空間計算量は O(1) で済みます（ソートアルゴリズム内部で使用されるメモリを除く）。