Pythonで部分文字列を削除して最大スコアをカウントするプログラム

文字列sと2つの値xとyがあるとします。与えられた2種類の操作を何度でも実行できます。

• サブストリング「ab」が存在する場合は、それを削除することでxポイントを獲得できます。

• サブストリング「ba」が存在する場合は、それを削除することでyポイントを獲得できます。

上記の操作をsに適用した後に獲得できる最大のポイントを見つける必要があります。

したがって、入力がs ="cbbaacdeabb" x =4 y =5の場合、最初の文字列は "cbbaacdeabb"であるため、出力は14になります。次に、 "cbbaacde（ab）b"を削除して4を取得し、文字列は " cbbaacdeb "、次に" cb（ba）acdeb "を削除して5を増やし、現在のスコア4 + 5 =9、文字列は" cbacdeb "になり、もう一度" c（ba）cdeb "を削除して、さらに5を取得します。スコア9+5 =14、文字列は「ccdeb」で、次に削除するものはありません。

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

• a：='a'、b：='b'
• ans：=0、a_st：=0、b_st：=0
• y> xの場合、
  • aとbを入れ替える
  • xとyを入れ替える
• sの各cについて、
  • cがaと同じ場合、
    • a_st：=a_st + 1
  • それ以外の場合、cがbと同じである場合、
    • a_stがゼロ以外の場合、
      • ans：=ans + x
      • a_st：=a_st-1
    • それ以外の場合、
      • b_st + =1
  • それ以外の場合、
    • ans：=ans +y*最小のa_stとb_st
    • a_st：=0
    • b_st：=0
• return ans +y*最小のa_stとb_st

例

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

def solve(s, x, y):
   a = 'a'
   b = 'b'
   ans = 0
   a_st = 0
   b_st = 0
   if y > x:
      a,b = b,a
      x,y = y,x
   for c in s:
      if c == a:
         a_st += 1
      elif c == b:
         if a_st:
            ans += x
            a_st -= 1
         else: b_st += 1
      else:
         ans += y * min(a_st, b_st)
         a_st = 0
         b_st = 0
   return ans + y * min(a_st, b_st)

s = "cbbaacdeabb"
x = 4
y = 5
print(solve(s, x, y))

入力

"cbbaacdeabb", 4, 5

出力

14