E - 地図の塗り分け / Map Coloring 解説 by admin
gemini-3.5-flash-high概要
一見すると、木DP（木上の動的計画法）を用いて解く非常に複雑な問題に見えますが、数学的な考察（境界値の評価）を行うことで、実は「すべての辺の重みの最小値を求めるだけ」の非常にシンプルな問題に帰着できることが分かります。
考察
1. 「2種類以上の色を使う」という条件の言い換え
すべての区画に同じ色を塗ることは許されません。これは、木の中に「両端の区画の色が異なる辺」が少なくとも1つ存在することと同値です。
2. 違和感コストの下限
両端の区画の色が異なる辺を \(e = (u, v)\) とします。 この辺の両端に割り当てられた色をそれぞれ \(a, b\) (\(a \neq b\)) とすると、この辺における違和感コストは \(W_e \times |a - b|\) となります。
\(a, b\) は相異なる整数であるため、その差の絶対値は少なくとも \(1\) 以上です（\(|a - b| \ge 1\)）。 したがって、この辺で発生するコストは少なくとも \(W_e\) 以上になります。
他のすべての辺で発生するコストは \(0\) 以上であるため、どのような塗り分け方（2種類以上の色を使用）に対しても、全体の違和感コストの合計は少なくとも \(\min_{e} W_e\) 以上になります。
3. 下限の達成可能性
では、違和感コストの合計をちょうど \(\min_{e} W_e\) にすることは可能でしょうか？
重みが最小である辺を \(e_{\min}\) とします。 木から辺 \(e_{\min}\) を取り除くと、木は2つの連結成分（部分木）に分かれます。 一方の連結成分に含まれるすべての区画に色 \(1\) を塗り、もう一方の連結成分に含まれるすべての区画に色 \(2\) を塗ることにします。
このとき、各辺で発生するコストは以下のようになります： - 辺 \(e_{\min}\)：両端の色が \(1\) と \(2\) なので、コストは \(W_{\min} \times |1 - 2| = W_{\min}\) - それ以外のすべての辺：両端が同じ色（ともに \(1\)、またはともに \(2\)）なので、コストは \(0\)
この塗り分け方において、使用した色は \(1\) と \(2\) の \(2\) 種類（\(K \ge 2\) より可能）であり、条件を満たします。 そして、このときの違和感コストの合計はちょうど \(W_{\min}\) となります。
4. 結論
以上の考察より、条件を満たす塗り分け方のうち、違和感コストの合計の最小値は、与えられたすべての辺の重み \(W_i\) の最小値にほかならないことが示されました。
アルゴリズム
提示されたコードは、この最小値を木DP（動的計画法）の形で愚直にシミュレーションして求めています。
DPの定義
- \(dp[u][c]\) : 頂点 \(u\) を色 \(c\) で塗ったときの、部分木 \(u\) における最小コスト。
遷移
子ノード \(v\) から親ノード \(u\) への遷移を考えます。 素直に遷移を計算すると、各色 \(c\) に対して \(g[c] = \min_{c'} (dp[v][c'] + W \times |c - c'|)\) を求める必要があり、普通にループを回すと \(O(K^2)\) かかります。
提示されたコードでは、絶対値記号を外すために、左右からの累積 \(\min\)（配列 L と R）を事前に計算しておくことで、この遷移を \(O(K)\) に高速化しています。
- \(L[c] = \min_{c' \le c} (dp[v][c'] - W \times c')\)
- \(R[c] = \min_{c' \ge c} (dp[v][c'] + W \times c')\)
これを用いることで、各 \(c\) に対する遷移後のコスト \(g[c]\) は以下のように \(O(1)\) で求まります： $\(g[c] = \min(W \times c + L[c], -W \times c + R[c])\)$
そして、DPテーブルの更新式は以下のようになっています：
dp[u][c] = min({ dp[u][c], g[c], W })
ここで、辺の重み \(W\) 自体との \(\min\) を取っている部分がポイントです。これは「この辺を境界として色を切り替える（コスト \(W\) を支払う）」という選択肢に対応しています。
この操作を葉から順に行うことで、最終的に根における dp[0][c] の値は、木全体の辺の重みの最小値 \(\min W_i\) に収束します。
計算量
提示されたDPコードの計算量
- 時間計算量: \(O(N K)\) 各頂点において、色数 \(K\) のループを回すため。
- 空間計算量: \(O(N K)\)
DPテーブル
dp[N][K]を保持するため。
注意: 問題の制約 \(K \le 10^8\) においては、提示されたコードはメモリ制限（MLE）および実行時間制限（TLE）に達します。しかし、上記の考察（最小値を出力するだけ）を用いることで、以下のように劇的に高速化できます。
最適化した解法の計算量
単にすべての辺の重みの最小値を求めるだけなので、グラフを構築する必要すらありません。 - 時間計算量: \(O(N)\) （入力の読み込みのみ） - 空間計算量: \(O(1)\)
実装のポイント
1. 遷移の高速化テクニック（左右からの累積 \(\min\)）
提示されたコード内の L と R を使った遷移は、「傾きが一定のコスト関数を加える木DP」における典型的な高速化テクニックです。\(K\) が小さい場合には非常に強力な手法となります。
2. 究極の簡略化
本問題の制約 \(K \le 10^8\) を満たして正解（AC）を得るためには、DPを実装する代わりに、以下のようにすべての辺の重みの最小値を直接出力するだけで十分です。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
long long K;
if (!(cin >> N >> M >> K)) return 0;
long long min_W = 1e18; // 十分に大きな値で初期化
for (int i = 0; i < M; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
min_W = min(min_W, w);
}
cout << min_W << "\n";
return 0;
}
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
int N, M, K;
vector<vector<pair<int, long long>>> adj;
vector<vector<long long>> dp;
void dfs(int u, int p) {
for (auto [v, W] : adj[u]) {
if (v == p) continue;
dfs(v, u);
vector<long long> L(K), R(K), g(K);
L[0] = dp[v][0];
for (int c = 1; c < K; ++c) {
L[c] = min(L[c-1], dp[v][c] - W * c);
}
R[K-1] = dp[v][K-1] + W * (K-1);
for (int c = K-2; c >= 0; --c) {
R[c] = min(R[c+1], dp[v][c] + W * c);
}
for (int c = 0; c < K; ++c) {
g[c] = min(W * c + L[c], -W * c + R[c]);
}
for (int c = 0; c < K; ++c) {
dp[u][c] = min({ dp[u][c], g[c], W });
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> M >> K)) return 0;
adj.resize(N);
for (int i = 0; i < M; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
--u; --v;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dp.assign(N, vector<long long>(K, INF));
dfs(0, -1);
long long ans = INF;
for (int c = 0; c < K; ++c) {
ans = min(ans, dp[0][c]);
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-high によって生成されました。
投稿日時:
最終更新: