Pythonで最初のn個の自然数の順列からマジックセットの数を求めるプログラム

問題の概要

最初のn個の自然数からなる配列Aと、その一つの順列P{p1, p2, ..., pn}が与えられます。このとき、以下の条件を満たす「マジックセット」と呼ばれる順列が全部でいくつ存在するかを求めます。

• 谷（局所最小値）の条件：位置a[1], a[2], ..., a[k]にある要素は、両隣の要素よりも小さくなければなりません。すなわち、P[a[i] - 1] > P[a[i]] < P[a[i] + 1] を満たします。
• 山（局所最大値）の条件：位置b[1], b[2], ..., b[l]にある要素は、両隣の要素よりも大きくなければなりません。すなわち、P[b[i] - 1] < P[b[i]] > P[b[i] + 1] を満たします。

例として、入力が n = 4、k = 1、l = 1、k_vals = [2]、l_vals = [3] の場合を考えてみましょう。このとき出力は 5 となります。N = 4、a[1] = 2、b[1] = 3 の条件下で条件を満たす順列は、[2,1,4,3]、[3,2,4,1]、[4,2,3,1]、[3,1,4,2]、[4,1,3,2] の5通り存在するためです。

解法の考え方

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。全体の手順は以下の通りです。

1. 答えが非常に大きな値になる可能性があるため、剰余計算用の定数 p := 10^9+7 を用意します。
2. サイズ n+2 の配列Fを0で初期化して作成します。Fは各位置が「谷」（1）か「山」（-1）かを記録する役割を持ちます。
3. k_valsの各要素aに対し、F[a - 1]またはF[a + 1]がすでに1になっている場合は条件の矛盾が発生するため、pをnullにします。矛盾がなければF[a] := 1 を設定します。
4. l_valsの各要素bに対し、F[b]が1、あるいはF[b - 1]・F[b + 1]が-1になっている場合は矛盾が発生するため、pをnullにします。矛盾がなければF[b] := -1 を設定します。
5. pがnullになった場合は、条件を満たす順列が一つも存在しないため0を返します。
6. 矛盾がない場合は、DPテーブルA・B・FFを構築して条件を満たす順列の総数を計算し、最後にA[n]を返します。

DPの詳細な仕組み

差分配列 FF[i] = F[i] - F[i - 1] を計算することで、「i番目の要素がi-1番目の要素より大きくなければならないのか（昇順）、それとも小さくなければならないのか（降順）」を判定できます。ここでA[j]は、「先頭からi個の数字を並べたとき、末尾の要素が利用可能な数字の中でj番目に小さいような並べ方の総数」を表します。遷移式は次のようになります。

• FF[i] > 0（昇順が必要）のとき：B[j] = (B[j - 1] + A[j - 1]) mod p
• FF[i] < 0（降順が必要）のとき：B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) mod p
• それ以外（制約なし）のとき：B[j] = (B[j - 1] + A[i - 1]) mod p

各ステップの終了時にAとBを入れ替えることで、メモリを節約しながら計算を進められます。

実装例

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

def solve(n, k, l, k_vals, l_vals):
   p = 10**9+7
   F = [0] * (n + 2)
   for a in k_vals:
      if F[a - 1] == 1 or F[a + 1] == 1:
         p = None
      F[a] = 1
   for b in l_vals:
      if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
         p = None
      F[b] = -1
   if p == None:
      return 0
   else:
      A = [0] * (n + 1)
      B = [0] * (n + 1)
      FF = [None] * (n + 1)
      for i in range(1, n + 1):
         FF[i] = F[i] - F[i - 1]
      A[1] = 1
      for i in range(2, n + 1):
         for j in range(1, i + 1):
            if FF[i] > 0:
               B[j] = (B[j - 1] + A[j - 1]) % p
            elif FF[i] < 0:
               B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
            else:
               B[j] = (B[j - 1] + A[i - 1]) % p
         A, B = B, A
      return A[n]

n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))

入力

4, 1, 1, [2], [3]

出力

5