ABC346 D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが開催している、競技プログラミングコンテストのことです。

今回はABC346のD問題を解説していきます。

ABC346　D – Gomamayo Sequence

問題

問題

0, 1からなる長さNの文字列Sが与えられます。

Sに操作を行い、一箇所のみ0か1が隣接し、それ以外の箇所は0と1が交互に並ぶ「良い文字列」にしたいです。（例：0100101）

操作とは、i文字目の0と1を反転させることです。それぞれのiに対し、この反転操作のコスト \(C_i \) が決まっています。

Sを「良い文字列」にするために必要なコストの総和の最小値を求める問題です。

制約

• \(2 \leqq N \leqq 2×10^5 \)
• \(1 \leqq C_i \leqq 10^9 \)

思考の筋道

DPを使って解きましょう。

各インデックスiに対し、今の文字が0と1のどちらか、それまでに隣接が発生したかどうかで、4種類の値を管理します。

これをもとに、漸化式を作成しましょう。

例えば、i+1文字目が0の場合は、次の4本の漸化式となります。

• dp[i + 1][0][0] = dp[i][1][0]
  i+1文字目の反転なし、これまでに隣接なしのパターン。
• dp[i + 1][1][0] = dp[i][0][0] + C[i]
  i+1文字目の反転あり、これまでに隣接なしのパターン。
  反転コストがかかる。
• dp[i + 1][0][1] = min(dp[i][1][1], dp[i][0][0])
  i+1文字目の反転なし、これまでに隣接ありのパターン。
  今回隣接が発生した場合と、過去に隣接が発生した場合で小さい方を取る。
• dp[i + 1][1][1] = min(dp[i][0][1], dp[i][1][0]) + C[i]
  i+1文字目の反転あり、これまでに隣接ありのパターン。
  今回隣接が発生した場合と、過去に隣接が発生した場合で小さい方を取る。
  反転コストがかかる。

N = int(input())
S = input()
C = list(map(int, input().split()))

INFTY = 2 ** 31 - 1
dp = [[[INFTY] * 2 for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 0
dp[0][1][0] = 0

for i in range(N):
    if S[i] == "0":
        dp[i + 1][0][0] = dp[i][1][0]
        dp[i + 1][1][0] = dp[i][0][0] + C[i]
        if i >= 1:
            dp[i + 1][0][1] = min(dp[i][1][1], dp[i][0][0])
            dp[i + 1][1][1] = min(dp[i][0][1], dp[i][1][0]) + C[i]
    else:
        dp[i + 1][0][0] = dp[i][1][0] + C[i]
        dp[i + 1][1][0] = dp[i][0][0]
        if i >= 1:
            dp[i + 1][0][1] = min(dp[i][1][1], dp[i][0][0]) + C[i]
            dp[i + 1][1][1] = min(dp[i][0][1], dp[i][1][0])

print(min(dp[N][0][1], dp[N][1][1]))

リンク