Pythonで指定したサイズ・合計・要素の上限を満たす重複なし配列を作成する方法

問題の概要

サイズを表す変数 N、配列内の全要素の合計を表す変数 SUM、そして「どの要素も K を超えてはならない」という上限を表す変数 K が与えられます。このとき、すべての要素が互いに異なる配列を見つけるのが目的です。条件を満たす配列が存在しない場合は -1 を返します。

例として、N = 4、SUM = 16、K = 9 が入力された場合、出力は [1, 2, 4, 9] となります。この配列は要素数が4、合計が16、最大値が9以下であり、すべての要素が重複なく並んでいます。

解法のアプローチ

この問題は、「理論上の最小合計・最大合計による実現可能性の判定」と「貪欲法（グリーディ法）による配列の構築」という2段階で解くことができます。

ステップ1：実現可能性の判定

N 個の相異なる正整数の合計が取りうる範囲をあらかじめ求めておきます。

• 最小合計： 1 + 2 + … + N = N × (N + 1) ÷ 2
• 最大合計： K + (K − 1) + … + (K − N + 1) = N × K − N × (N − 1) ÷ 2

SUM がこの範囲より小さければ、どのような組み合わせでも合計を下回ることはできません。逆に範囲を超えていれば、上限 K を守りながら目標の合計に到達できません。したがって、次のいずれかに当てはまる場合は解が存在しないとして -1 を返します。

• minimum_sum > SUM の場合
• maximum_sum < SUM の場合

ステップ2：貪欲法による配列の構築

まず、最小の配列 [1, 2, …, N] を初期状態とします。その後、大きい側のインデックスから順に、現在の上限値 K への置き換えを試みます。「K に置き換えても合計が SUM を超えない」間は置き換えを続け、超える瞬間に残りの差分だけをその位置の要素へ加算して配列を完成させます。

• minimum_sum := (N * (N + 1)) / 2 を計算する
• maximum_sum := (N * K) - (N * (N - 1)) / 2 を計算する
• minimum_sum > SUM または maximum_sum < SUM ならば -1 を返す
• res := 0 から N までの連続した値で初期化したサイズ N+1 の配列を用意する
• sum := minimum_sum とし、i := N から処理を開始する
• i が 1 以上である限り、以下を繰り返す
  • x := sum + (K - i) を計算する
  • x < SUM ならば、sum に (K - i) を加え、res[i] := K として K を 1 減らす
  • そうでなければ、res[i] に (SUM - sum) を加算し、sum := SUM としてループを抜ける
• 各反復の最後に i を 1 減らす
• 最後に res を返す

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

def get_arr(N, SUM, K):
    # 実現可能な合計の範囲を計算
    minimum_sum = (N * (N + 1)) / 2
    maximum_sum = (N * K) - (N * (N - 1)) / 2

    # 範囲外なら解なし
    if (minimum_sum > SUM or maximum_sum < SUM):
        return -1

    # 初期配列 [0, 1, 2, ..., N]
    res = [i for i in range(N + 1)]
    current_sum = minimum_sum
    i = N

    while i >= 1:
        x = current_sum + (K - i)
        if x < SUM:
            # i番目の要素を現在の最大値Kに置き換え
            current_sum = current_sum + (K - i)
            res[i] = K
            K -= 1
        else:
            # 残りの差分を加算して配列を完成させる
            res[i] += (SUM - current_sum)
            current_sum = SUM
            break
        i -= 1

    return res

N = 4
SUM = 16
K = 9
print(get_arr(N, SUM, K))

入力と出力

入力：

4, 16, 9

出力：

[0, 1, 2, 4.0, 9]

出力結果の読み方と注意点

返される配列のインデックス 0 はダミーであり、実際の答えはインデックス 1 以降の要素 [1, 2, 4.0, 9] です。また、除算に「/」を使用しているため、結果の一部が浮動小数点数（4.0 など）になります。整数として扱いたい場合は、整数除算「//」に置き換えるとよいでしょう。

さらに注意したいのは、ループカウンタ i の減算位置です。i -= 1 を break 文の後ろや if-else ブロックの内側に書いてしまうと、減算が実行されず無限ループや誤った結果につながる可能性があります。上記の実装例では、i -= 1 を if-else ブロックの外側に配置することで、毎回確実にカウンタが減るようにしています。