Pythonで方程式を成立させるために必要な最小の数字挿入回数を求めるプログラム

文字列 s が与えられ、これは x+y=z の形式で表される方程式を意味するとします。このとき、s に数字を挿入して等式が正しく成立するようにするために必要な、最小の挿入回数を求めるのがこの問題です。

例えば、入力が s = '2+6=7' の場合、出力は 2 になります。

これは、「1」と「2」を挿入することで方程式を「21+6=27」に書き換えられるためです。つまり、必要な修正回数は合計2回となります。

解法のアプローチ

この問題は、桁ごとの繰り上がりを考慮した動的計画法（DP）を用いて解くことができます。手順は以下の通りです。

• 文字列 s を「+」記号で分割し、左側を A、右側を rest とします。

• rest を「=」記号で分割し、左側を B、右側を C とします。

• dp(サイズA - 1, サイズB - 1, サイズC - 1, 0) を返します。

関数 dp() の定義

引数として i、j、k、carry（繰り上がり）を受け取る関数 dp() を定義します。

• i <= -1 かつ j <= -1 かつ k <= -1 の場合、carry が 0 なら 0 を、そうでなければ 1 を返します。

• last1 := i >= 0 なら A[i]、それ以外は 0

• last2 := j >= 0 なら B[j]、それ以外は 0

• last3 := k >= 0 なら C[k]、それ以外は 0

• prefix1 := i >= 0 なら A[0 から i+1 まで]、それ以外は 0

• prefix2 := j >= 0 なら B[0 から j+1 まで]、それ以外は 0

• prefix3 := k >= 0 なら C[0 から k+1 まで]、それ以外は 0

• i <= -1 かつ j <= -1 の場合：

  • rhs := prefix3 - carry

  • rhs <= 0 であれば、|rhs| を返します。

  • i == -1 または j == -1 の場合、文字列 rhs の長さを返します。

  • それ以外の場合は False を返します。

• k <= -1 の場合、str(prefix1 + prefix2 + carry) の長さを返します。

• ans := 無限大 で初期化します。

• carry2, lhs := divmod(carry + last1 + last2, 10) で商と余りを求めます。

• lhs == last3 の場合、ans := dp(i - 1, j - 1, k - 1, carry2) とします。

• req := last3 - carry - last2、extra_zeros := max(0, -1 - i)、carry2 := req < 0 なら 1、それ以外は 0 とし、ans := min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2)) を更新します。

• 同様に req := last3 - carry - last1、extra_zeros := max(0, -1 - j)、carry2 := req < 0 なら 1、それ以外は 0 とし、ans := min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2)) を更新します。

• carry2, lhs := divmod(last1 + last2 + carry, 10) を計算し、ans := min(ans, 1 + dp(i - 1, j - 1, k, carry2)) を更新します。

• 最後に ans を返します。

メインメソッドからは dp(サイズA - 1, サイズB - 1, サイズC - 1, 0) を返します。

実装例

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

class Solution:
    def solve(self, s):
        A, rest = s.split("+")
        B, C = rest.split("=")
        def dp(i, j, k, carry):
            if i <= -1 and j <= -1 and k <= -1:
                return 0 if carry == 0 else 1
            last1 = int(A[i]) if i >= 0 else 0
            last2 = int(B[j]) if j >= 0 else 0
            last3 = int(C[k]) if k >= 0 else 0
            prefix1 = int(A[: i + 1]) if i >= 0 else 0
            prefix2 = int(B[: j + 1]) if j >= 0 else 0
            prefix3 = int(C[: k + 1]) if k >= 0 else 0
            if i <= -1 and j <= -1:
                rhs = prefix3 - carry
                if rhs <= 0:
                    return abs(rhs)
                if i == -1 or j == -1:
                    return len(str(rhs))
                else:
                    assert False
            if k <= -1:
                return len(str(prefix1 + prefix2 + carry))
            ans = float("inf")
            carry2, lhs = divmod(carry + last1 + last2, 10)
            if lhs == last3:
                ans = dp(i - 1, j - 1, k - 1, carry2)
            req = last3 - carry - last2
            extra_zeros = max(0, -1 - i)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
            req = last3 - carry - last1
            extra_zeros = max(0, -1 - j)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
            carry2, lhs = divmod(last1 + last2 + carry, 10)
            ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
            return ans
        return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print (ob.solve('2+6=7'))

入力

'2+6=7'

出力

2