ABC解説

ABC344 D問題の解説（Python）

はじめに

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

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

ABC344　D – String Bags

問題

問題

空文字列Sがあります。また、文字列がいくつか入った袋1, 2, …, Nがあります。各袋 \(i\) には \(A_i\) 個の文字列 \(S_{i,1}, S_{i,2}, …, S_{i,N}\) が入っています。

袋1, 2, …, Nの順に一度ずつ、以下のどちらかの処理を行います。

  • 1円を支払うことで、その袋から文字列を一つだけ選択し、Sの末尾に連結する
  • 何もしない

文字列Tが与えられるとき、最終的にSとTを一致させるために必要な最小の金額を求める問題です。なお、どのようにしても最終的なSをTに一致させることができない場合、-1と出力します。

制約

  • \(1 \leqq len(T) \leqq 100\)
  • \(1 \leqq N \leqq 100\)
  • \(1 \leqq A_i \leqq 10\)
  • \(1 \leqq len(S_{i,j}) \leqq 10\)

思考の筋道

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

遷移性のある最大値・最小値・個数を求める問題はDP（動的計画法）を検討しましょう！

dpの設定
  • i：何袋目か
  • j：何文字目まで出来上がったか
  • dp[i][j]：この条件で必要な最小の金額

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

  • dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
    袋を使わないパターン。
  • dp[i + 1][j + len(s)] = min(dp[i][j] + 1, dp[i + 1][j + len(s)])
    袋から文字列sを取り出し連結するパターン。
    ただし、連結させることでTに近づくようなsのみを考えます。

最終的に、dp[N][len(T)]が必要な金額の最小値です。

漸化式を立てる際はどのような遷移のパターンがあるかを考えることが重要ですね。

コード

T = input()
N = int(input())

INF = 10 ** 9
dp = [[INF for _ in range(len(T) + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    S = list(input().split())[1:]
    for j in range(len(T) + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        for s in S:
            if s == T[j:j + len(s)]:
                dp[i + 1][j + len(s)] = min(dp[i][j] + 1, dp[i + 1][j + len(s)])

if dp[N][len(T)] < INF:
    print(dp[N][len(T)])
else:
    print(-1)

リンク

ABC344