Pythonでn回の操作後に最大スコアを求めるプログラム（ビットマスクDP解説）

問題概要

サイズが 2*n の配列 nums があるとします。この配列に対して、合計 n 回の操作を行います。i 番目の操作（1始まりのインデックス）では、以下の手順を実行します。

• 配列から2つの要素 x と y を選択する。
• i * gcd(x, y) のスコアを獲得する。
• 選んだ x と y を配列 nums から削除する。

n 回すべての操作を終えたときに得られる最大スコアを求めるのが目標です。

たとえば、入力が nums = [6,2,1,5,4,3] の場合、出力は 14 になります。最適な選び方は次の通りです。

(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

解決アプローチ：ビットマスクDP（メモ化再帰）

この問題は、各要素が「使用済みかどうか」をビットフラグで管理し、メモ化再帰によって全組み合わせを探索することで効率的に解けます。状態数は最大 2^n 通りなので、単純な全順列の試行よりも大幅に計算量を抑えられます。

アルゴリズムの手順

• n := nums のサイズとする。
• dp := サイズ 2^n の配列を作成し、すべて -1 で初期化する（メモ化用）。
• 関数 dfs(mask, t) を定義する。mask は使用済み要素の集合、t は現在の操作回数を表す。
• mask が (2^n - 1) と等しい場合（すべての要素を使用済み）、0 を返す。
• dp[mask] が -1 でない場合（計算済み）、dp[mask] を返す。
• ma := 0 で初期化する。
• i を 0 から n-1 までループする。
  • (2^i AND mask) が 0 でない場合（i 番目の要素が使用済み）、次の反復へスキップ。
  • j を i+1 から n-1 までループする。
    • (2^j AND mask) が 0 でない場合、次の反復へスキップ。
    • next := dfs(mask OR 2^i OR 2^j, t + 1) + gcd(nums[i], nums[j]) * t を計算。
    • ma := next と ma の大きい方を採用。
• dp[mask] := ma を記録し、dp[mask] を返す。
• メイン処理からは dfs(0, 1) の結果を返す。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

from math import gcd

def solve(nums):
    n = len(nums)
    dp = [-1] * (1 << n)

    def dfs(mask, t):
        if mask == (1 << n) - 1:
            return 0
        if dp[mask] != -1:
            return dp[mask]
        ma = 0
        for i in range(n):
            if (1 << i) & mask:
                continue
            for j in range(i + 1, n):
                if (1 << j) & mask:
                    continue
                next = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t
                ma = max(next, ma)
        dp[mask] = ma
        return dp[mask]

    return dfs(0, 1)

nums = [6,2,1,5,4,3]
print(solve(nums))

入力

[6,2,1,5,4,3]

出力

14

計算量について

状態数は最大 2^n 個あり、各状態ごとに未使用ペアの組み合わせを最大 O(n^2) で調べるため、時間計算量は O(2^n × n^2)、空間計算量はメモ化テーブル分の O(2^n) となります。n が小さい範囲（おおよそ 20 以下）であれば現実的な時間で求解できます。