1799. Maximize Score After N Operations

Dailyで出てきたHardの問題。

https://leetcode.com/problems/maximize-score-after-n-operations/description/

解説を見るとビットマスキングとDPを使っていて難しい。

もっと単純に、素直に解けたので備忘録。もちろん最適解ではない。

成約を見ると以下の通りである。

1 <= n <= 7
nums.length == 2 * n

最大でもn=14のため、O(n^5)程度なら全探索が許容されそうなので、問題文に書いてあることを素直に実装していく。

メモ化再帰を使うため、引数はイミュータブルであるタプルに変換しておく。

スライシングは、Kをスライスする長さとした時にO(K)の計算量が必要となるが、前述の通り最大でも14なのでTLEにはならない。

gcdのスコアを計算する2つの要素を2重ループで全探索し、残りの要素をrestとして再帰処理していく。

import math
from functools import lru_cache


class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums) // 2
        nums = tuple(sorted(nums))


        @lru_cache(maxsize=None)
        def rec(nums_tuple, n_operation):
            m = len(nums_tuple)
            
            if m == 0:
                return 0
            
            maxScore = 0
            for i in range(m):
                for j in range(i+1, m):
                    rest = nums_tuple[:i] + nums_tuple[i+1:j] + nums_tuple[j+1:]
                    score = math.gcd(nums_tuple[i], nums_tuple[j]) * n_operation
                    score += rec(rest, n_operation + 1)
                    maxScore = max(maxScore, score)
            
            return maxScore
        

        ans = rec(nums, 1)

        return ans