Pythonプログラム：2つのリストを厳密に増加列にするための最小スワップ回数を求める

同じ長さを持つ2つの数値リストAとBが与えられているとします。ここで、A[i]とB[i]の値を入れ替える(スワップする)という操作を実行できるものとします。このとき、両方のリストを厳密に増加する列(各要素が直前の要素より必ず大きい列)にするために必要な最小の操作回数を求めるのがこの問題です。

例えば、入力が A = [2, 8, 7, 10]、B = [2, 4, 9, 10] の場合、出力は 1 になります。これは、Aの「7」とBの「9」を一度だけ入れ替えることで、A = [2, 8, 9, 10]、B = [2, 4, 7, 10] となり、どちらのリストも厳密に増加する列になるからです。

解決アプローチ：動的計画法(DP)

この問題は、再帰的な動的計画法を用いて効率的に解くことができます。以下の手順に従います。

• 関数 dp() を定義します。引数として現在のインデックス i と、直前の位置でスワップを行ったかどうかを示すフラグ prev_swapped を受け取ります。
• Aのサイズがiと等しい場合(すべての要素を処理し終えた場合)：0を返します。
• iが0の場合(先頭の要素の場合)：min(dp(i + 1, False), 1 + dp(i + 1, True)) を返します。つまり、「スワップしない場合」と「スワップする場合」のうち、操作回数が少ない方を選択します。
• それ以外の場合:
  • prev_A := A[i - 1]、prev_B := B[i - 1] を設定します。
  • prev_swapped がTrueの場合、prev_A と prev_B の値を入れ替えます(実際に前のステップでスワップされていた値を反映するため)。
  • A[i] <= prev_A または B[i] <= prev_B の場合：現状のままでは厳密な増加列にならないため、現在の位置でスワップするしか選択肢がありません。1 + dp(i + 1, True) を返します。
  • それ以外の場合:
    • ans := dp(i + 1, False)(スワップしない場合の結果)
    • A[i] > prev_B かつ B[i] > prev_A の場合、スワップしても成立するため、ans = min(ans, 1 + dp(i + 1, True)) としてより小さい方を採用します。
    • ans を返します。
• メインメソッドから dp(0, False) を呼び出し、その戻り値を結果として返します。

それでは、以下の実装例を見て理解を深めましょう。

サンプルコード

class Solution:
   def solve(self, A, B):
      def dp(i=0, prev_swapped=False):
         if len(A) == i:
            return 0
         elif i == 0:
            return min(dp(i + 1), 1 + dp(i + 1, True))
         else:
            prev_A = A[i - 1]
            prev_B = B[i - 1]
            if prev_swapped:
               prev_A, prev_B = prev_B, prev_A
            if A[i] <= prev_A or B[i] <= prev_B:
               return 1 + dp(i + 1, True)
            else:
               ans = dp(i + 1)
            if A[i] > prev_B and B[i] > prev_A:
               ans = min(ans, 1 + dp(i + 1, True))
            return ans

      return dp()

ob = Solution()
A = [2, 8, 7, 10]
B = [2, 4, 9, 10]
print(ob.solve(A, B))

入力

[2, 8, 7, 10], [2, 4, 9, 10]

出力

1

このアルゴリズムでは、各位置において「スワップする・しない」の2つの選択肢を探索しながら、直前の状態(スワップ済みかどうか)を考慮することで、全体として最小の操作回数を正しく求めることができます。