AtCoder が提供しているABC（AtCoder Beginner Contest）344 のD問題をC++とPythonで解いてみました。ABC344は、2024年3月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 String Bags（Difficulty : 854）
問題はリンク先をご覧ください。
DPで解くことができます。AtCoder Problems による Difficulty は 854 でした。
解答案
DPで解くことができます。dp[i][j] を袋を i 個を処理した後に 文字列 T の j 文字目まで一致している最小の支払い金額とします。
出力する回答は、dp[N][Tの長さ] となります。
漸化式は、以下となります。
- なにもしない場合：
i を小さい方から処理して、すべての j に対して
dp[i+1][j] = dp[i][j] - 袋 i から、文字を取り出して T の j 文字目の直前と一致している場合：
dp[i+1][j] = dp[i][j – 取り出した文字列の長さ] + 1
ただし、最小値となる場合のみ更新する。
初期値は、以下となります。
- dp[0][0] = 0
- それ以外の場合は、無限大（十分に大きな値とする）
問題の見た目は異なりますが、ナップザック問題と同じ構造になっています（部分文字列が一致している条件がありますが）。
C++ プログラム例（ABC344D）
上で解説した漸化式を実装しました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
string t;
cin >> t;
int n;
cin >> n;
vector<vector<string>> a(n);
for (int i = 0; i < n; ++i) {
int size;
cin >> size;
for (int j = 0; j < size; ++j) {
string temp;
cin >> temp;
a[i].push_back(temp);
}
}
int ts = t.length();
vector<vector<int>> dp(n + 1, vector<int>(ts + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= ts; ++j) {
dp[i + 1][j] = dp[i][j];
for (int k = 0; k < a[i].size(); ++k) {
int len = a[i][k].length();
if ((j - len >= 0)&&(t.substr(j - len, len) == a[i][k])) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - len] + 1);
}
}
}
}
if (dp[n][ts] == INF) {
cout << -1 << endl;
} else {
cout << dp[n][ts] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC344D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 344 D"""
INF = 1 << 30
t = input()
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
a[i] = list(input().split())
del a[i][0]
ts = len(t)
dp = [[INF for _ in range(ts + 1)] for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
for j in range(ts + 1):
dp[i + 1][j] = dp[i][j]
for k in range(len(a[i])):
len_s = len(a[i][k])
if j - len_s >= 0 and t[j - len_s:j] == a[i][k]:
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - len_s] + 1)
print(-1 if dp[n][ts] == INF else dp[n][ts])こちらも「AC」と判定されました。
最後に
この問題は、In-Placeに書いて1次元で計算したらWA判定されました。コンテスト中には、ACを取ることができませんでした。素直に2次元で書けばよかったと思います。
引き続き ABC の問題を紹介していきます。
