Pythonで2つのリストの最終インデックスに到達するための最小コストを求めるプログラム

問題の概要

同じ長さを持つ2つの数値リスト nums0 と nums1、および距離を表す d と切り替えコストを表す c の2つの値が与えられているとします。

私たちはどちらかのリストのインデックス0からスタートし、どちらかのリストの最終インデックスに到達することを目標とします。各ターンでは、次の2つの操作が可能です。

• コスト c を支払って、もう一方のリストに切り替える
• 最大 d だけ前方へジャンプする(着地したインデックスの値がその分のコストとして加算される)

このとき、タスクを完了するために必要な合計コストの最小値を求める必要があります。

入力例

nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3

出力例

18

この結果が18になる理由は以下の通りです。まず最初のリストの値「2」からスタートし、2番目のリストに切り替えて「4」へ移動、さらに最初のリストに戻って「6」でゴールします。着地コストは 2 + 4 + 6 = 12、リストの切り替えは2回行ったので 3 × 2 = 6、合計は 12 + 6 = 18 となります。

解法のアプローチ

この問題は再帰的な探索によって解くことができます。手順は以下の通りです。

• キー0に nums0、キー1に nums1 を対応付けたマップ switch を作成する
• インデックス idx とリスト番号 nums を引数にとる関数 search() を定義する
• idx がリストのサイズ以上の場合、無限大(inf)を返す
• idx がリストの最終インデックスと一致する場合、その位置の値を返す
• それ以外の場合、1 から dist + 1 までの範囲でループを行い、「同じリスト内でジャンプする場合」と「コストを払って別のリストに切り替えてジャンプする場合」の2パターンの最小値を計算する
• メイン処理では、search(0, 0) と search(0, 1) のうち小さい方を結果として返す

Pythonによる実装例

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

class Solution:
    def solve(self, nums0, nums1, dist, cost):
        switch = {0: nums0, 1: nums1}
        def search(idx, nums):
            if idx >= len(switch[nums]):
                return float("inf")
            if idx == len(switch[nums]) - 1:
                return switch[nums][-1]
            c = float("inf")
            for i in range(1, dist + 1):
                c = min(c, switch[nums][idx] + search(idx + i, nums))
                c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
            return c
        return min(search(0, 0), search(0, 1))

ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c))

入力

[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3

出力

18

まとめ

このプログラムでは、再帰を使って「同じリスト内で前進する」「切り替えコストを支払って別のリストへ移る」という選択肢をすべて試し、その中で最小のコストを見つけています。なお、入力サイズが大きくなる場合は、同じ (idx, nums) の組み合わせに対する計算結果をキャッシュすることで、計算量を大幅に削減できます。