ABC344 D問題の解説（Python）

はじめに

この記事では、ABC344のD問題を解説していきます。

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

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[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のD問題の解説でした！

では、またね。

リンク