AtCoder Grand Contest 012 B - Splatter Painting

問題

 1からNまでの番号がついたN個の頂点とM本の辺からなる単純無向グラフが与えられる。全ての頂点ははじめ色0で塗られているとし、次のような色を塗る操作をQ回行う。i回目の操作では頂点v_iから距離d_i以内にあるような頂点たち全ての色を色c_iで上書きする。Q回の操作後に各頂点がどの色で塗られているかを示せ。

解法

 1時間半ほど考えたがとっかかりも掴めないような有様だったので諦めて解説PDFを読んだ。

 操作を逆順に見ると一度塗られたものは確定する。この性質を利用して動的計画法を考える。\mathrm{dp}(v,d)を「頂点vから距離d以内にある頂点たちの色を塗るという操作が行われた時点」とする。頂点vから距離d以内にある頂点を塗るという操作を再帰的に展開することでこのテーブルは埋めることができる。

 最終的に頂点vの色は\mathrm{dp}(v,0)の操作における色である。

反省

 重要な点は

  • 操作を逆順に見ると一度塗られたものは確定する
  • 頂点だけではなく残り距離も含めて一つの状態とする

 ことだと思われる。一つ目はすぐに考えたが二つ目が思い浮かばなかった。イメージとしてはICPCでよくある「ノード数に時間などの違う要素を付け加えて拡張する」ような感じだろうか。ICPCではその後ダイクストラ法を適用することが多い印象だが、結局はそれも動的計画法なのであり、計算過程で状態を一意に識別できるように情報を増やすという点が本質なのだと思う。

 解説PDFでは操作回数を記録することによって後で色を参照するような書きぶりになっているが、直接色を記録していっても良い。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

vector<vector<ll>> connect;
vector<vector<ll>> color;

void update(ll v, ll d, ll i) {
    if (color[v][d] != 0) {
        return;
    }
    color[v][d] = i;
    if (d == 0) {
        return;
    }
    update(v, d - 1, i);
    for (auto next : connect[v]) {
        update(next, d - 1, i);
    }
}

int main() {
    ll N, M;
    cin >> N >> M;

    connect.resize(N);
    for (ll i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }

    ll Q;
    cin >> Q;
    vector<ll> v(Q), d(Q), c(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> v[i] >> d[i] >> c[i];
        v[i]--;
    }

    color.assign(N, vector<ll>(11, 0));
    for (ll i = Q - 1; i >= 0; i--) {
        update(v[i], d[i], c[i]);
    }
    for (ll i = 0; i < N; i++) {
        cout << color[i][0] << endl;
    }
}