AtCoder

ABC271 E問題(Subsequence Path)を解く

AtCoder_ABC271_E

AtCoder が提供しているABC(AtCoder Beginner Contest)271 のE問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

E問題 Subsequence Path(Difficulty : 1402)

問題はリンク先をご覧ください。

ABC271 E問題 Subsequence Path

グラフの問題ではなく、良い経路に着目したDPで解きます。AtCoder Problems による Difficulty は、1402 でした。

解答案

問題を読むと、グラフの問題のように見えます。

ただし、頂点1から頂点$N$までのすべての経路を列挙して、その経路が数列$E$の部分列になる場合の辺の長さの最小値は?、という発想では解けません。経路の候補が多すぎるためです。

数列$E$に着目して、数列$E$の部分列の経路を通り、頂点1から頂点$N$までの辺の長さの最小値は?という考えで解いてみます。部分和問題に近いかもしれません。

$DP_{i,j}$ を頂点1から頂点$j$まで行く経路で、数列 $E_i$ までの要素 $(E_1, E_2, \cdots, E_i)$ の部分列となる場合の辺の長さの最小値とします。

まず、すべての $j$ に対して、以下の漸化式で初期化します。

$$DP_{i+1, j} = DP_{i, j}$$

次に $A_{E_{i+1}} \rightarrow B_{E_{i+1}} $ の辺の長さが $C_{E_{i+1}}$ であることを使うと、以下の漸化式で更新できます(左辺との最小値を取る必要がありますが)。

$$DP_{i+1, B_{E_{i+1}}} = DP_{i, A_{E_{i+1}}} + C_{E_{i+1}}$$

初期値は、

$$DP_{i, 1} = 0,\; DP_{i, j}\; (1 \leqq i \leqq M,\; j \neq 1)$$

となります。

C++ プログラム例(ABC271E)

$DP$ は二次元で説明しましたが、次の $i+1$ の $DP$ を更新するために $i$ の値をベースとしているため、in-plase で書き換えることができます(23、26行目)。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define INF (1ULL << 60)

int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(m), b(m);
	vector<ll> c(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i] >> c[i];
	}
	vector<int> e(k);
	for (int i = 0; i < k; ++i) {
		cin >> e[i];
		--e[i];
	}

	vector<ll> dp(n + 1, INF);
	dp[1] = 0;
	for (int i = 0; i < k; ++i) {
		if (dp[a[e[i]]] < INF) {
			dp[b[e[i]]] = min(dp[b[e[i]]], dp[a[e[i]]] + c[e[i]]);
		}
	}

	if (dp[n] >= INF) {
		cout << -1 << endl;
	} else {
		cout << dp[n] << endl;
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC271E)

Python 版も基本的な考え方は同じです。以下がそのプログラムです。

"""AtCoder Beginner Contest 271 E"""
INF = 1 << 60
n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(int, input().split())
e = list(map(int, input().split()))
for i in range(k):
    e[i] -= 1

dp = [INF] * (n + 1)
dp[1] = 0
for i in range(k):
    if dp[a[e[i]]] < INF:
        dp[b[e[i]]] = min(dp[b[e[i]]], dp[a[e[i]]] + c[e[i]])

print(dp[n] if dp[n] < INF else -1)

Python 版も「AC」と判定されました。

最後に

ABC271に参加した時には、DPはまったく解けませんでした。この問題は読むことすらできませんでした。

一見するとグラフの問題に見えます。見た目に惑わされず本質的な問題の構造が読み取れれば、DPとして解くことができたと考えています。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA