Pythonですべてのペアが「良いペア」となる部分列の最大サイズを求めるプログラム

サイズ n の数列 nums が与えられます。この中から、任意のペア (p, q) がすべて「良いペア(nice pair)」となるような nums の部分列の最大サイズを求めることを考えます。

あるペアが「良いペア」であるとは、次の条件のうち少なくとも1つを満たす場合を指します。

1. p が持つ相異なる素因数の個数の偶奇が、q のそれと一致する。たとえば 18 の相異なる素因数は 2 と 3 の2つです。
2. p の正の約数の総和の偶奇が、q のそれと一致する。

たとえば、入力が nums = [2,3,6,8] のとき、出力は 3 になります。

解き方の手順

この問題を解くには、次の手順に従います。

• n := nums のサイズとする
• 空のリスト cnt、total、result を用意する
• nums の各要素 i について、以下を実行する
  • count := 0、tot := 0 で初期化する
  • 空のリスト prime を作成し、nums の各要素 j のうち素数であるものを格納する
  • prime の各要素 j について、i が j で割り切れる場合は count を1増やす
  • count が奇数なら cnt に 'odd' を、偶数なら 'even' を追加する
  • 1 から i までの各 j について、i が j で割り切れる場合は tot に j を加算する
  • tot が奇数なら total に 'odd' を、偶数なら 'even' を追加する
• i を 0 から n-2 まで、j を i+1 から n-1 まで動かしながら、cnt[i] と cnt[j] が等しい、または total[i] と total[j] が等しい場合に result に nums[i] を追加する(j が n-1 のときは nums[j] も追加する)
• result から重複を取り除いた集合を作り、そのサイズを返す

実装例

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

def solve(nums):
    n = len(nums)
    cnt = []
    total = []
    result = []
    for i in nums:
        count = 0
        tot = 0

        prime = []
        for j in nums:
            if all(j % k for k in range(2, j)) == True:
                prime.append(j)

        for j in prime:
            if i % j == 0:
                count += 1
        if count % 2:
            cnt.append('odd')
        else:
            cnt.append('even')

        for j in range(1, i + 1):
            if i % j == 0:
                tot += j

        if tot % 2:
            total.append('odd')
        else:
            total.append('even')

    for i in range(n - 1):
        for j in range(i + 1, n):
            if cnt[i] == cnt[j] or total[i] == total[j]:
                result.append(nums[i])
                if j == n - 1:
                    result.append(nums[j])

    result = list(set(result))
    return len(result)

nums = [2, 3, 6, 8]
print(solve(nums))

入力

nums = [2,3,6,8]

出力

3

結果の解説

各要素を分類すると、次のようになります。

• 2: 素因数は {2}(奇数個)、約数の総和は 1+2=3(奇数)
• 3: 素因数は {3}(奇数個)、約数の総和は 1+3=4(偶数)
• 6: 素因数は {2, 3}(偶数個)、約数の総和は 1+2+3+6=12(偶数)
• 8: 素因数は {2}(奇数個)、約数の総和は 1+2+4+8=15(奇数)

このうち部分列 [2, 3, 8] は、どのペアも素因数の個数の偶奇が一致しているため、すべてのペアが「良いペア」となるサイズ3の部分列となります。これが最大であるため、答えは 3 になります。