Pythonで部分配列を並べ替えて等差数列にできるか判定するプログラム

数列 nums と、サイズ m の2つの配列 l および r が与えられます。l と r は [l[i], r[i]] のような範囲クエリを表しています。ここで求めたいのは、ブール値のリスト ans です。ans[i] は、nums[l[i]] から nums[r[i]] までの部分配列を並べ替えて等差数列(算術数列)を作れる場合に True、そうでない場合に False となります。

等差数列とは、少なくとも2つの要素から構成され、隣接する2つの要素同士の差がすべて等しい数列のことです。たとえば、[2, 4, 6, 8, 10]、[5, 5, 5, 5]、[4, -2, -8, -14] などは等差数列ですが、[2, 2, 3, 6, 9] は等差数列ではありません。

たとえば、入力が nums = [6,8,7,11,5,9]、l = [0,0,2]、r = [2,3,5] の場合、出力は [True, False, True] になります。その理由は次のとおりです。

• クエリ [0, 2] の場合:対象の数列は [6,8,7] であり、[6,7,8] と並べ替えられるため有効(True)

• クエリ [0, 3] の場合:対象の数列は [6,8,7,11] であり、どのように並べ替えても等差数列にはならない(False)

• クエリ [2, 5] の場合:対象の数列は [7,11,5,9] であり、[5,7,9,11] と並べ替えられるため有効(True)

解決のためのアプローチ

この問題を解くために、以下の手順に従います。

• new := l と同じサイズのリストを作成し、すべて True で初期化する

• i を 0 から l のサイズ - 1 まで繰り返す:

  • data := nums のインデックス l[i] から r[i] までの部分リストを取り出す

  • data を昇順にソートする

  • d := 空の新しいリストを用意する

  • j を 0 から data のサイズ - 2 まで繰り返し、d の末尾に data[j+1] - data[j](隣接要素の差)を追加する

  • d := d から生成したセット(set)をもとに新しいリストを作る(重複を除去)

  • d のサイズが 1 でない場合(= 差が複数種類ある場合):

    • new[i] := False とする

• 最後に new を返す

アルゴリズムのポイント

このアプローチの核心は、等差数列の性質にあります。数列を昇順にソートした後、隣接する要素間の差がすべて同一であれば、その数列は必ず等差数列として並べ替え可能です。差分を集合(set)に格納して重複を除去することで、「差が1種類のみであるか」を簡単に判定できます。各クエリあたりの計算量は、部分配列の長さを k とすると O(k log k)(ソートのコストが支配的)となります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums, l, r):
    new = [True]*len(l)

    for i in range(len(l)):
        data = nums[l[i]:r[i]+1]
        data.sort()

        d = []
        for j in range(len(data) - 1):
            d.append(data[j+1] - data[j])

        d = list(set(d))
        if len(d) != 1:
            new[i] = False
    return new

nums = [6,8,7,11,5,9]
l = [0,0,2]
r = [2,3,5]
print(solve(nums, l, r))

入力

[6,8,7,11,5,9], [0,0,2], [2,3,5]

出力

[True,False,True]