Pythonで辞書式順序が最大の山型リストを求めるプログラム

問題の概要

正の整数 n、lower、upper の3つが与えられたとします。このとき、次の条件をすべて満たすリストを考えます。

• 長さがちょうど n である
• 前半は狭義単調増加、後半は狭義単調減少という「山」の形状になっている
• すべての要素が範囲 [lower, upper](両端を含む)に収まっている
• 増加部分と減少部分がどちらも空ではない

これらの条件を満たすリストの中から、辞書式順序で最も大きなものを1つ求めてください。条件を満たすリストが存在しない場合は、空のリストを返します。

たとえば n = 5、lower = 3、upper = 7 のとき、答えは [6, 7, 6, 5, 4] となります。一見すると [7, 6, 5, 4, 3] も有効に思えますが、このリストは最初から最後まで単調に減少しているだけで増加部分が存在しないため、条件を満たしません。

解法のアプローチ

まず、山型リストが取りうる最大の長さを考えます。値の幅を c = upper − lower とおくと、増加部分に使える異なる値は最大 c + 1 個、減少部分も同じく最大 c + 1 個です。両者は頂上(ピーク)の値を共有するため、山型リストの長さは最大でも 2 × (upper − lower) + 1 です。したがって、n がこの値を超える場合は答えが存在せず、空のリストを返します。

辞書式順序を最大化するには、先頭の要素をできる限り大きくすることが重要です。ピークは必ず upper に置くのが最適で、その手前の増加部分は必要最小限の長さに抑えます。具体的な手順は以下の通りです。

1. n > 2 × (upper − lower) + 1 の場合は、空のリストを返す
2. c = upper − lower とする
3. d = 1 で初期化する
4. c < n の場合は、d = n − c − 1 と更新する
5. d が 0 になった場合は、d = 1 に戻す
6. 増加部分 f を range(upper − d, upper)、つまり upper − d から upper − 1 までの昇順リストとして作成する
7. 減少部分 g を range(upper, upper − n + d, −1)、つまり upper から降順に n − d 個の要素を持つリストとして作成する
8. f と g を連結して返す

Pythonでの実装例

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

def solve(n, lower, upper):
    if n > 2 * (upper - lower) + 1:
        return []
    c = upper - lower
    d = 1
    if c < n:
        d = n - c - 1
    if d == 0:
        d = 1
    f = list(range(upper - d, upper))
    g = list(range(upper, upper - n + d, -1))
    return f + g

n = 5
lower = 3
upper = 7
print(solve(n, lower, upper))

入力

5, 3, 7

出力

[6, 7, 6, 5, 4]

処理の流れを確認

n = 5、lower = 3、upper = 7 のケースを追いかけてみます。まず c = 7 − 3 = 4 となります。c < n なので d = 5 − 4 − 1 = 0 となり、さらに d = 1 に修正されます。よって f = [6]、g = [7, 6, 5, 4] となり、これらを連結した [6, 7, 6, 5, 4] が出力されます。

計算量

リストの構築は一度の走査で完了するため、時間計算量・空間計算量はともに O(n) です。