Pythonでリスト内の全ペアの連結値の合計を求めるプログラム

数値のリスト nums が与えられたとき、リスト内のすべてのペアについて連結した値の合計を求めることを考えます。ここで重要なのは、ペア (i, j) とペア (j, i) は異なるものとして扱うという点です。

問題の例

例えば、入力が nums = [5, 3] の場合、出力は 176 になります。考えられる連結は次の4通りです。

• (nums[0], nums[0]) → 5 と 5 の連結 → 55
• (nums[0], nums[1]) → 5 と 3 の連結 → 53
• (nums[1], nums[0]) → 3 と 5 の連結 → 35
• (nums[1], nums[1]) → 3 と 3 の連結 → 33

これらを合計すると、55 + 53 + 35 + 33 = 176 となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。ポイントはメモ化（キャッシュ）を活用し、同じ値との連結計算を繰り返さないようにすることです。

memo := 新しい辞書（マップ）
nums1 := nums
temp := 0
c := nums1 の全要素の合計
a := nums のサイズ

for i in range 0 to a, do
    if nums[i] == 0, then
        temp := temp + c
    otherwise,
        if nums[i] is present in memo, then
            temp := temp + memo[nums[i]]
        otherwise,
            b := 0
            for j in range 0 to a, do
                b := b + integer of (nums[i] concatenate nums1[j])
            memo[nums[i]] := b
            temp := temp + memo[nums[i]]
return temp

要素が 0 の場合に特別な処理を行っているのは、0 と任意の数値 x を連結しても（例：「0」と「5」で「05」）、整数としては元の値 x と等しくなるため、リスト全体の合計 c をそのまま加算できるからです。

実装例

より理解を深めるために、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, nums):
        memo = {}
        nums1 = nums
        temp = 0
        c = sum(nums1)
        a = len(nums)
        for i in range(a):
            if nums[i] == 0:
                temp += c
            else:
                if nums[i] in memo:
                    temp += memo[nums[i]]
                else:
                    b = 0
                    for j in range(a):
                        b += int(str(nums[i]) + str(nums1[j]))
                    memo[nums[i]] = b
                    temp += memo[nums[i]]
        return temp

ob = Solution()
nums = [5, 3]
print(ob.solve(nums))

入力

[5, 3]

出力

176

まとめ

このアルゴリズムでは、各要素について他のすべての要素との連結結果を一度だけ計算し、辞書にキャッシュすることで計算量を削減しています。リスト内に重複した値が多い場合に特に効果を発揮します。時間計算量は O(n²)、空間計算量は O(n) となります。