【Python】正n角形の頂点から条件を満たす「特別なサブセット」の数を数える方法

配列 colors があり、これは1つの正n角形の各頂点の色を表しているとします。この多角形の各頂点には、配列内に存在するn種類の色の中からランダムに1色が割り当てられています。ここで、次の条件をすべて満たす「特別なサブセット」の数を求める必要があります。

• サブセットのサイズは2以上であること。
• サブセットに含まれる頂点を多角形から取り除くと(それらの頂点に隣接する辺も同時に削除されます)、残った頂点と辺がいくつかの連続したパスを形成すること。
• どのパスにも、同じ色の頂点が2つ以上含まれていないこと。

そのようなサブセットの総数を数えます。答えが非常に大きくなる場合は、10^9 + 7 で割った余りを返してください。

たとえば、入力が colors = [1,2,3,4] の場合、出力は 11 になります。

アルゴリズムの考え方

まず、サイズが2以上のすべての部分集合を、組み合わせの数 nCr(n, i)(i = 2 ～ n)の総和として数え上げます。この段階ではまだ条件を考慮していない、全パターンが含まれた状態です。

次に、同じ色が複数回現れている場合を検証します。同じ色の頂点ペアごとに、時計回りの距離 d1 と反時計回りの距離 d2 を計算し、どちらかが n-3 以下であれば、そのペアが削除後に同一の連続パス上に残ってしまう可能性があるため、該当するサブセットを1つずつ差し引いていきます。最終的に残った値が答えとなります。

解法の手順

• count := 値が空のリストであるマップ(辞書)を用意します。
• n := colors のサイズ
• i を 0 から colors のサイズ - 1 まで繰り返し、i を count[colors[i]] の末尾に追加します。
• answer := 0
• i を 2 から n まで繰り返し、answer := answer + nCr(n, i) を行います。
• count のすべてのキー i について以下を繰り返します。
  • l0 := count[i]、n0 := l0 のサイズ
  • n0 > 1 の場合、i を 0 から n0-2 まで、j を i+1 から n0-1 まで二重ループで回します。
    • d1 := l0[j] - l0[i]、d2 := l0[i] - l0[j] + n
    • d1 <= n-3 または d2 <= n-3 の場合、answer := answer - 1
• answer を返します。

実装例

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

from collections import defaultdict
from math import factorial

def nCr(n, i):
   if n==1:
      return 1
   return factorial(n)//factorial(i)//factorial(n-i)

def solve(colors):
   count = defaultdict(list)
   n = len(colors)

   for i in range(len(colors)):
      count[colors[i]].append(i)
   answer = 0

   for i in range(2, n+1):
      answer += nCr(n, i)

   for i in count.keys():
      l0 = count[i]
      n0 = len(l0)

      if n0 > 1:
         for i in range(n0-1):
            for j in range(i+1, n0):
               d1 = l0[j] -l0[i]
               d2 = l0[i] -l0[j] + n
               if d1 <= n-3 or d2<= n-3:
                  answer -=1

   return answer

colors = [1,2,3,4]
print(solve(colors))

入力

[1,2,3,4]

出力

11

まとめ

このアルゴリズムは、まず組み合わせによって候補となる全サブセットを数え上げ、その後、同色の頂点ペアの位置関係(周上での距離)をチェックすることで条件違反のケースを除外するというシンプルな発想に基づいています。頂点数 n に対して組み合わせ計算とペア検証を行うため、実装も直感的で理解しやすいのが特徴です。