Pythonのバイナリ文字列から10または01を削除することで、最大スコアを取得する方法を見つけるプログラム

バイナリ文字列sと2つの値zero_oneとone_zeroがあるとします。ここで、サブストリング「01」を削除してzero_oneポイントを受け取ることができる操作について考えてみましょう。または、サブストリング「10」を削除して、one_zeroポイントを受け取ることもできます。任意の数の操作の後に取得できるポイントの最大数を見つける必要があります。

したがって、入力がs ="10100101" zero_one =3 one_zero =2の場合、「01」を3回削除して3 * 3 =9ポイントを取得できるため、出力は11になります。次に、残りの文字列は10です。これを削除すると、さらに2ポイントを取得できるため、合計は11になります。

これを解決するには、次の手順に従います-

• A：=入力文字列として指定されたビットのリスト

• zero_one

  • zero_oneとone_zeroを入れ替える

  • 0からAのサイズの範囲のiの場合、実行

    • A [i]：=A [i] XOR 1

• ans：=0

• スタック：=新しいスタック

• Aのxごとに、実行します

  • スタックが空ではなく、スタックの最上位要素が

    • スタックからポップ

    • ans：=ans + zero_one

  • それ以外の場合

    • xをスタックにプッシュ

• ans：=ans +one_zero*スタックでの0の発生とスタックでの1の発生の最小値

• ansを返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, S, zero_one, one_zero):
      A = list(map(int, S))
      if zero_one < one_zero:
         zero_one, one_zero = one_zero, zero_one
         for i in range(len(A)):
            A[i] ^= 1
         ans = 0
         stack = []
         for x in A:
            if stack and stack[-1] < x:
               stack.pop()
               ans += zero_one
            else:
               stack.append(x)
         ans += one_zero * min(stack.count(0), stack.count(1))
         return ans
ob = Solution()
s = "10100101"
zero_one = 3
one_zero = 2
print(ob.solve(s, zero_one, one_zero))

入力

"10100101", 3, 2

出力

11