E - 都市巡りとミッション達成 / City Tour and Mission Completion 解説 by admin
gemini-3.5-flash-thinking概要
本問題は、都市1から出発して制限時間 \(T\) 以内にいくつかの都市を訪問し、達成できたミッションの報酬の合計を最大化する問題です。
ミッションに関係する都市の種類数が高々 \(14\) と非常に小さいことに着目し、ダイクストラ法による最短経路の算出と、巡回セールスマン問題（TSP）に類似したビットDP（動的計画法）を組み合わせることで、効率的に解くことができます。
考察
1. 注目すべき「重要な都市」の絞り込み
都市の総数 \(N\) や道路の数 \(M\) は最大で \(10^4\) と大きいですが、ミッションの条件に関わる都市の総数は \(\bigcup_{j=1}^{K} S_j \le 14\) と非常に小さいです。 スタート地点である都市 \(1\) を含めても、私たちが訪問を考慮すべき「重要な都市」は高々 \(15\) 個しかありません。これ以外の都市は、重要な都市の間を移動するための単なる「経由地」としてしか機能しません。
したがって、この \(15\) 個以下の重要な都市の集合を \(V_{\text{imp}}\) とすると、問題は以下のように分解できます。 1. \(V_{\text{imp}}\) に含まれる任意の \(2\) 都市間の最短移動時間を求める。 2. 求めた最短移動時間を用いて、制限時間 \(T\) 以内に \(V_{\text{imp}}\) のどの部分集合を訪問可能かを調べる。
2. 都市間の最短距離の計算
\(V_{\text{imp}}\) のサイズを \(V_{\text{size}}\) とします（\(V_{\text{size}} \le 15\)）。
各重要都市から他のすべての都市への最短距離は、ダイクストラ法を \(V_{\text{size}}\) 回実行することで求められます。
これにより、重要都市 \(u\) から \(v\) への最短移動時間 dist[u][v] をすべての \(u, v \in V_{\text{imp}}\) について得ることができます。
3. ビットDPによる訪問可能パターンの探索
訪問した重要都市の集合をビット列（mask）で管理します。
\(V_{\text{size}} \le 15\) であるため、訪問状態の総数は \(2^{15} = 32768\) 通りしかありません。
以下のような動的計画法（DP）を定義します。
- dp[mask][u] : これまでに訪問した重要都市の集合が mask であり、現在重要都市 u にいるときの、移動時間の最小値。
初期状態は、都市1（インデックスを start_idx とする）のみを訪問し、そこにいる状態です。
- dp[1 << start_idx][start_idx] = 0
- それ以外の値は \(\infty\) で初期化します。
遷移は、現在地 \(u\) から未訪問の重要都市 \(v\) へ移動することを考えます。
- dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])
4. 報酬の最大化
DPの計算が完了した後、すべての mask について、制限時間 \(T\) 以内にその訪問状態を達成可能かを判定します。
具体的には、\(\min_{u} \text{dp[mask][u]} \le T\) を満たす mask が達成可能です。
達成可能な mask それぞれについて、どのミッションが達成できているかをビット演算で判定し、得られる報酬の合計を計算します。その中の最大値が答えとなります。
アルゴリズム
重要都市の列挙と座標圧縮 各ミッションの対象都市および都市 \(1\) を集め、重複を排除した配列 \(V_{\text{imp}}\) を作成します。 各都市番号を \(V_{\text{imp}}\) 内のインデックス（\(0\) から \(V_{\text{size}} - 1\)）に変換（座標圧縮）し、各ミッションの条件 \(S_j\) もビットマスク
mission_mask[j]に変換しておきます。最短経路の計算 \(V_{\text{imp}}\) の各都市を始点としてダイクストラ法を計 \(V_{\text{size}}\) 回実行し、重要都市間の隣接行列
distを構築します。ビットDPの実行 前述の遷移式に従って、
dp[mask][u]を更新します。答えの集計 各
maskについて、制限時間 \(T\) 以内に到達可能であれば、獲得できる報酬を計算し、その最大値を更新します。 ミッション \(j\) が達成できているかは、(mask & mission_mask[j]) == mission_mask[j]で判定できます。
計算量
時間計算量
- ダイクストラ法: \(O(V_{\text{size}} \cdot (N + M) \log N)\) \(V_{\text{size}} \le 15\) であるため、この部分は十分に高速です。
- ビットDP: \(O(2^{V_{\text{size}}} \cdot V_{\text{size}}^2)\) \(V_{\text{size}} = 15\) のとき、状態遷移のループ回数は最大で約 \(32768 \times 15^2 \approx 7.3 \times 10^6\) 回となり、実行時間制限に余裕で間に合います。
- 報酬の集計: \(O(2^{V_{\text{size}}} \cdot K)\) 最大で約 \(32768 \times 100 \approx 3.2 \times 10^6\) 回の判定です。
全体の時間計算量は \(O(V_{\text{size}} (N + M) \log N + 2^{V_{\text{size}}} (V_{\text{size}}^2 + K))\) となり、実行時間制限（通常 2.0 秒）に対して十分高速に動作します。
空間計算量
- グラフの隣接リスト: \(O(N + M)\)
- 重要都市間の距離テーブル
dist: \(O(V_{\text{size}}^2)\) - DPテーブル
dp: \(O(2^{V_{\text{size}}} \cdot V_{\text{size}})\)
全体の空間計算量は \(O(N + M + 2^{V_{\text{size}}} \cdot V_{\text{size}})\) です。\(V_{\text{size}} \le 15\) のため、メモリ使用量は数メガバイト程度に収まります。
実装のポイント
都市1の追加を忘れない: ミッションに都市1が含まれていなくても、スタート地点である都市1は必ず最初に訪問済みとなるため、重要都市リスト \(V_{\text{imp}}\) に必ず含める必要があります。
型に注意: 移動時間 \(T\) や報酬 \(P_j\)、最短距離の累積値は非常に大きくなる可能性があるため、C++では
long long型を使用します。座標圧縮:
std::lower_boundを用いることで、元の都市番号から \(V_{\text{imp}}\) 内の \(0\) から始まるインデックスへの変換を簡単かつ高速に行うことができます。ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
const long long INF = 1e18;
vector<long long> dijkstra(int start, const vector<vector<pair<int, long long>>>& adj, int N) {
vector<long long> dist(N + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
long long T;
if (!(cin >> N >> M >> K >> T)) return 0;
vector<vector<pair<int, long long>>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
vector<vector<int>> S(K);
vector<long long> P(K);
set<int> imp_set;
for (int j = 0; j < K; ++j) {
int sz;
cin >> sz;
S[j].resize(sz);
for (int i = 0; i < sz; ++i) {
cin >> S[j][i];
imp_set.insert(S[j][i]);
}
cin >> P[j];
}
imp_set.insert(1);
vector<int> V_imp(imp_set.begin(), imp_set.end());
int V_size = V_imp.size();
int start_idx = lower_bound(V_imp.begin(), V_imp.end(), 1) - V_imp.begin();
vector<int> mission_mask(K, 0);
for (int j = 0; j < K; ++j) {
int mask = 0;
for (int u : S[j]) {
int idx = lower_bound(V_imp.begin(), V_imp.end(), u) - V_imp.begin();
mask |= (1 << idx);
}
mission_mask[j] = mask;
}
vector<vector<long long>> dist(V_size, vector<long long>(V_size, INF));
for (int i = 0; i < V_size; ++i) {
auto d = dijkstra(V_imp[i], adj, N);
for (int j = 0; j < V_size; ++j) {
dist[i][j] = d[V_imp[j]];
}
}
vector<vector<long long>> dp(1 << V_size, vector<long long>(V_size, INF));
dp[1 << start_idx][start_idx] = 0;
for (int mask = 1; mask < (1 << V_size); ++mask) {
for (int u = 0; u < V_size; ++u) {
if (dp[mask][u] >= INF) continue;
for (int v = 0; v < V_size; ++v) {
if (dist[u][v] >= INF) continue;
if (!((mask >> v) & 1)) {
int next_mask = mask | (1 << v);
if (dp[next_mask][v] > dp[mask][u] + dist[u][v]) {
dp[next_mask][v] = dp[mask][u] + dist[u][v];
}
}
}
}
}
long long max_reward = 0;
for (int mask = 0; mask < (1 << V_size); ++mask) {
bool reachable = false;
for (int u = 0; u < V_size; ++u) {
if (dp[mask][u] <= T) {
reachable = true;
break;
}
}
if (!reachable) continue;
long long reward = 0;
for (int j = 0; j < K; ++j) {
if ((mask & mission_mask[j]) == mission_mask[j]) {
reward += P[j];
}
}
max_reward = max(max_reward, reward);
}
cout << max_reward << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。