AtCoder Grand Contest 021 B - Holes

問題

 平面上にN個の点がある。半径 R = 10^{10^{10^{10}}}の円内から無作為に1箇所選んだとき、i番目の点が一番近くなる確率を求めよ。

解法

 Rが十分大きいので、細かい部分は無視されて点に吸い込まれる角度だけが重要となる。N個の点集合に関する凸包を求めて、その頂点となっている点について内角を求めればその頂点に入る角度がわかる。 f:id:tokumini:20180802111853p:plain

 制約が緩くO(N^{3})までは許されるためかなり手抜きの実装で良い。i番目の点から見て、端としてj番目の点を固定して、k番目の点を含めるのに時計回りで何度必要かというループを回すことで解ける。

f:id:tokumini:20180802111912p:plain

反省

 コンテスト時に解いた(および解説を読んだ)記憶がかなり残っていたので方針はすぐにわかったが、実装でかなり手間取った。O(N^{3})で良いのでかなり綺麗に書けることに気が付いて、開始から30分ほどでようやく実装できたがWA。

 どこが間違っているかわからなかったのでDropBoxに上げられているテストケースを見た。単に真下にある点に対する角度を間違って2\piとしていただけだった(\piが正しい)。最初は度数法で書いていたのを、acosラジアンで返すものだったので全てラジアンに修正した際に間違ってしまったのだった。基本的にラジアンで扱っていくのが良さそうか。

 定数\piを利用するためにconst double PI = acos(-1);ということをしたが、#define _USE_MATH_DEFINESを定義してからcmathを読み込めばM_PIという定義済みマクロが使えるようだ。

コード

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

int main() {
    const double PI = acos(-1);

    ll N;
    cin >> N;
    vector<double> x(N), y(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }

    //iからjへの角度を求める
    //真上が0度で時計回りに計測
    //iから見てi以外の点が全てある180度の中に収まっていたら凸包の頂点になる
    vector<vector<double>> angle(N, vector<double>(N));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }

            if (x[j] == x[i]) {
                if (y[j] > y[i]) {
                    angle[i][j] = 0.0;
                } else {
                    angle[i][j] = PI;
                }
            } else if (x[j] > x[i]) {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                angle[i][j] = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
            } else {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                double a = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
                angle[i][j] = 2.0 * PI - a;
            }
        }
    }

    vector<double> min_angles(N);
    for (ll i = 0; i < N; i++) {
        double min_angle = INT_MAX;
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }
            //iから見て、jを一番端としてここから全部の点を含めるのに時計回りで何度必要かを計算
            double tmp = 0;
            for (ll k = 0; k < N; k++) {
                if (k == i || k == j) {
                    continue;
                }
                if (angle[i][k] < angle[i][j]) {
                    tmp = max(tmp, angle[i][k] + 2.0 * PI - angle[i][j]);
                } else {
                    tmp = max(tmp, angle[i][k] - angle[i][j]);
                }
            }
            min_angle = min(min_angle, tmp);
        }

        min_angles[i] = min_angle;
    }

    for (ll i = 0; i < N; i++) {
        printf("%.10f\n", max(PI - min_angles[i], 0.0) / (2.0 * PI));
    }
}

SRM503 Div1 Easy - ToastXToast

問題

 パンがいくつかの種類に分かれている。ある種類のパンはX分でちょうど焼き上がり、それより短い焼き時間だとundertoasted、長い焼き時間だとovertoastedとなる。

 いくらかの種類のパンに対してundertoastedとなった焼き時間の列、overtoastedとなった焼き時間の列があたえられたとき、ありうるパンの種類数として最小値を求めよ。

解法

 可能性としてあるのは-1,1,2の3通りなのでundertoastedとovertoastedの最大、最小値を見て場合分けしていく。

反省

 30分ほどでAC。変に2分探索してずらしながら……とか考えていたので問題の仕組みに気づくのが遅かった。

 気づいてからもu_max >= o_maxの条件を入れ忘れていて1WA、入れたときに不等号の向きを逆にしてしまいさらに1WAという感じでひどかった。

コード

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

class ToastXToast {
public:
    int bake(vector<int> undertoasted, vector<int> overtoasted) {
        auto u_min = *min_element(undertoasted.begin(), undertoasted.end());
        auto u_max = *max_element(undertoasted.begin(), undertoasted.end());
        auto o_min = *min_element(overtoasted.begin(), overtoasted.end());
        auto o_max = *max_element(overtoasted.begin(), overtoasted.end());

        if (u_min >= o_min || u_max >= o_max) {
            return -1;
        } else if (u_max < o_min) {
            return 1;
        } else {
            return 2;
        }
    }
};

SRM502 Div1 Easy - TheLotteryBothDivs

問題

 000000000から999999999までの数字のうち一つが書いてある宝くじを一つ買う。vector<string>が与えられ、その要素のどれか一つでもsuffixになっていれば当選であるとき、当選する確率を求めよ。

解法

 同じだったり被ったりする要素を上手く弾くだけ。

 vector<string>を文字の長さが小さい順に見ていってsetに詰めながら被りを排除していけばいい。制約が緩いので何をやっても通りそう。

反省

 12分ほどでAC。解法を考えるところではあまり詰まらなかったけど実装の方針があまり良くなかったか。

コード

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

class TheLotteryBothDivs {
public:
    double find(vector<string> goodSuffixes) {
        sort(goodSuffixes.begin(), goodSuffixes.end(), [&](string lhs, string rhs) {
            return lhs.size() != rhs.size() ? lhs.size() < rhs.size() : lhs < rhs;
        });
        double ans = 0;
        set<string> used;
        for (auto str : goodSuffixes) {
            bool ok = true;
            for (int i = 0; i < str.size(); i++) {
                auto sub = str.substr(str.size() - i - 1);
                if (used.find(sub) != used.end()) {
                    //中にあったら意味ない
                    ok = false;
                    break;
                }
            }

            if (!ok) {
                continue;
            }

            ans += pow(0.1, str.size());
            used.insert(str);
        }

        return ans;
    }
};

AtCoder Grand Contest 018 B - Sports Festival

問題

 M個のスポーツに対してN人がそれぞれ1つだけに参加する。i番目の人の参加優先順位がA_{ij}で表されるとき、実施するスポーツを適切に選択して最も多くの人が参加するスポーツの参加人数を最小化せよ。

解法

 全てのスポーツを実施する状況から考える。このとき選択されるのは各行の一番左であり、各スポーツの参加人数がわかる。ここで一番参加人数の多いものを排除するとそこに参加していた人たちは違うスポーツに移ることになる。そこで再計算すればまた各スポーツの参加人数がわかり、また多いものを排除するということを繰り返していけば求まる。これはO(NM^{2})なので間に合う。

 詳細な証明は解説PDF参照のこと。

反省

 32分44秒でAC。最初はDPで解けるんじゃないかといろいろ状態の持ち方を工夫しようとしていたが上手くいかず、なんとなく全てのスポーツを実施する状況から考えて貪欲に排除していけばいいんじゃないかと適当に実装してサンプル流してみたら合っていたので提出。そのまま通ってしまい驚いた。ちゃんと理屈を考えずにとりあえず投げてしまうひどい解き方だった。

 AGCだと700点問題でもこういう感じのことがあり得るんだなぁ。順位表で解けた人数を見ると点数のわりに多めな気はする。

コード

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

int main() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> A(N, vector<ll>(M));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < M; j++) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }

    vector<bool> ok(M, true);
    ll ans = INT_MAX;

    for (ll i = 0; i < M; i++) {
        vector<ll> selected_num(M, 0);
        for (ll j = 0; j < N; j++) {
            for (ll k = 0; k < M; k++) {
                if (ok[A[j][k]]) {
                    selected_num[A[j][k]]++;
                    break;
                }
            }
        }

        ll max_num = 0, max_index = -1;
        for (ll j = 0; j < M; j++) {
            if (selected_num[j] > 0) {
                if (selected_num[j] > max_num) {
                    max_num = selected_num[j];
                    max_index = j;
                }
            }
        }

        ans = min(ans, max_num);

        ok[max_index] = false;
    }

    cout << ans << endl;
}

AtCoder Grand Contest 017 B - Moderate Differences

問題

 N個のマスが一列に並んでおり、一番左には整数A、一番右にはBが書き込まれているとする。どの隣接マスについても書かれている整数の差がC以上D以下であるように残りのマスを埋めることができるかどうか判定せよ。

解法

 Aから+[C, D]または-[C,D]のような操作をN - 1回行ったときBになるかどうかを考える。i回足す操作をすると残りのN - 1 - i回は引く操作をすることになり、それぞれ変動量の絶対値が大きくなるのは毎回Dを足し引きするとき、小さくなるのはCを足し引きするとき。最大と最小の間は足す量引く量を調節すれば自由に取れるので、結局
 \displaystyle A + i C - (N - 1 - i) D \le B \le A + i D - (N - 1 - i) C
i = 0, 1, \dots, N - 1のどれかで満たされていればいい。

 解説PDFも同じ。

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

int main() {
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;

    for (ll i = 0; i < N; i++) {
        //i回は大きくなり,N - 1 - i回は小さくなる
        ll max = A + i * D - (N - 1 - i) * C;
        ll min = A + i * C - (N - 1 - i) * D;
        if (min <= B && B <= max) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}

反省

 14分ちょいでAC。図を書いていたら足す回数、引く回数に着目する発想が出てきて、その後はすぐに解けた。こういうある操作の回数をiとして~という考え方はよくあるので重要だと思う。

 以下は考察中のメモ。右下で足す回数をxとしてやれば良さそうということに気づいている。それまでの図が有効だったかどうかは……わからない。

f:id:tokumini:20180730101202p:plain

AtCoder Grand Contest 014 B - Unplanned Queries

問題

 N頂点の木が与えられ、最初は全ての辺に0が書き込まれている。頂点a_i, b_iを結ぶパス上の全ての辺に対して書かれている数を+1するクエリM個あり、最終的に書かれた数が全て偶数になったとする。このような木が存在するかどうかを判定せよ。

解法

 (0-originとして)頂点0を根として考える。他の頂点は頂点0から距離1であるような木を考えたとき、これが条件を満たすかどうかの判定は各頂点がa_i, b_iに登場する回数を数えていけば簡単。このような木でできないとき、頂点0を根とすることは変えずに上手く繋ぎ変えても結局偶奇性の破綻は解消できないので、この判定が全て。

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

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

    vector<ll> edge_num(N, 0);
    for (ll i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        if (a > b) {
            swap(a, b);
        }

        if (a == 0) {
            edge_num[b]++;
        } else {
            edge_num[a]++;
            edge_num[b]++;
        }
    }

    for (ll i = 1; i < N; i++) {
        if (edge_num[i] % 2 != 0) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
}

反省・感想

 最初に考えた方針が当たって15分くらいでAC。しかし厳密な証明はしていなくて、なんとなくこれで通りそうという雰囲気による提出をしただけである。解説PDFで言われていることが一瞬理解できなかったが、ほぼ同じことを言っている。厳密な証明はこうやってやるのか。

 LCA(Lowest Common Ancestor:最近共通祖先)という考え方は重要そうだ。頂点u, vに対して根をrootとすると \displaystyle d(u, v) = d(root, u) + d(root, v) - 2 d(root, LAC(u,v))という式が成り立つというのも覚えておいた方がよさそう。

 木が出てきたら根を適当に決めて考えてみるというのが頭に浮かんだ瞬間解けたので、これも良かった。

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)

A問題

 2倍していきながら範囲内に被る数を数えていけば十分間に合う。

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

int main() {
    ll C, D;
    cin >> C >> D;

    ll ans = 0;
    for (ll i = 0;; i++) {
        ll low = 140 * pow(2, i);
        ll high = 170 * pow(2, i);
        if (low >= D) {
            break;
        }
        if (high <= C) {
            continue;
        }
        ans += min(D, high) - max(low, C);
    }

    cout << ans << endl;
}

B問題

問題

 N個の要素を持つ配列bが与えられる。連続して並ぶK個の薬品を0とする操作を繰り返したとき、和を最大化せよ。

解法

 DPを考えて、i番目を0にしないような最大値、左側に0がK-1個続くような最大値の2つを保持しながら計算していくと上手く遷移が取れるので計算できる。コンテスト中の提出時はもっと無駄の多いコードを書いていたがもっと洗練させることができた。以下は修正後のもの。

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

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> b(N);
    for (ll i = 0; i < N; i++) {
        cin >> b[i];
    }

    //1-originとして
    //dp[i][0] := b[i]を0としない[0, i]までの和の最大値
    //dp[i][1] := b[i]を0とする[0, i]までの和の最大値
    vector<vector<ll>> dp(N + 1, vector<ll>(2, INT_MIN));

    dp[0][0] = 0;
    dp[0][1] = 0;

    //(i - K, i]を0にするという操作を考える

    //i < Kでは0にする操作ができないので0としないものを求めるだけ
    for (ll i = 1; i < K; i++) {
        dp[i][0] = dp[i - 1][0] + b[i - 1];
    }

    for (ll i = K; i <= N; i++) {
        //0にしない場合直前までの大きい方にb[i - 1]を足すだけ
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + b[i - 1];

        //0にする場合
        //(1)直前を0としていたらここだけを0にできる
        //(2)直前を0にしていなかったらK個前まで戻る
        dp[i][1] = max(dp[i - 1][1], max(dp[i - K][0], dp[i - K][1]));
    }

    cout << max({ dp[N][0], dp[N][1] }) << endl;
}

反省

 こういうDPをなんとか書けたのは多少成長を感じる。計算過程で必要なものを考察して、それを上手く持ちながら計算していけたので良かった。

AtCoder Grand Contest 013 B - Hamiltonish Path

問題

 N頂点M辺の連結な単純無向グラフについて、

  • 2個以上の頂点を通る
  • 同じ頂点を2度以上通らない
  • パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

 という条件を満たすパスを1つ見つけて出力せよ。

解法

 1時間半ほど考えてもさっぱりわからなかったので解説PDFを読んだ。

 適当なパスを作り条件を満たしていなかったら伸ばすことを繰り返していくと、最終的にはN頂点を覆うパスができるのでいつかは条件が満たされる。条件を満たしているかの判定にかかる計算量も高々O(M)なのでこれで間に合う。

 解説PDFの手法をかなり愚直めに実装したら1515msecで結構危なかった。

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

int main() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> connect(N);
    vector<ll> ans;

    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);

        if (i == 0) {
            ans.push_back(A);
            ans.push_back(B);
        }
    }

    vector<bool> visit(N, false);
    visit[ans[0]] = true;
    visit[ans[1]] = true;

    auto isOK = [&]() {
        for (auto n : connect[ans.front()]) {
            if (!visit[n]) {
                return false;
            }
        }
        for (auto n : connect[ans.back()]) {
            if (!visit[n]) {
                return false;
            }
        }
        return true;
    };

    while (!isOK()) {
        bool add = false;
        for (auto n : connect[ans.back()]) {
            if (!visit[n]) {
                ans.push_back(n);
                visit[n] = true;
                add = true;
                break;
            }
        }
        if (add) {
            continue;
        }
        for (auto n : connect[ans.front()]) {
            if (!visit[n]) {
                ans.insert(ans.begin(), n);
                visit[n] = true;
                break;
            }
        }
    }

    cout << ans.size() << endl;
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
    }
}

反省

 見当違いの考察しかできていなかった。基本的に考えていたのはもとのグラフの次数に注目したことで、次数1のノードが2つあればそれらを繋いでいけばいいし、1つでもそれを片方の端点には使っていいだろうという感じ。次数2以上のノードしかないときは、サイクルができるはずなのでそれを上手く加工すれば条件が満たされるのではないか……と思っていたが、その先がさっぱりわからなかった。

 解説の方法は、貪欲法と言われればそうなのかもしれないけどなかなかこれを上手く思いつける気がしない。しかし具体例を構成するタイプの問題ではこの手の解法は定跡だったりするのかもしれない。ダメなものをどう加工すれば良くなるか、という視点が重要だったのだろうか。しかし1回増やしただけで条件を満たすわけではなく、最終的には満たす状態になりうる~という感じの解法はなかなか難しいように思える。

Apery(WCSC28)の評価関数パラメータを読み込む

 開発中の将棋ソフトについて、評価関数部分以外の性能を強豪ソフトと比較するため、評価関数パラメータを読み込む機能を実装した。

 AperyとはBonaPieceにおいて持ち駒0枚に数字を割り振っているかどうかや、盤上の駒を示す順番が角→馬→飛車→竜か角→飛車→馬→竜かという細かい違いはあったが、読み込んだのちパラメータを格納するタイミングで吸収できる。BonaPiece(海底ではPieceState)の変換は、洗練されていないコードになるが、次のようにした。

    auto changeToAperyPieceState = [&](int64_t p) {
        if (p >= white_hand_rook) {
            if (black_rook <= p && p < black_horse) {
                p += 81 * 2;
            } else if (black_horse <= p && p < black_dragon) {
                p -= 81 * 2;
            }
            return p + 14;
        } else if (p >= black_hand_rook) {
            return p + 13;
        } else if (p >= white_hand_bishop) {
            return p + 12;
        } else if (p >= black_hand_bishop) {
            return p + 11;
        } else if (p >= white_hand_gold) {
            return p + 10;
        } else if (p >= black_hand_gold) {
            return p + 9;
        } else if (p >= white_hand_silver) {
            return p + 8;
        } else if (p >= black_hand_silver) {
            return p + 7;
        } else if (p >= white_hand_knight) {
            return p + 6;
        } else if (p >= black_hand_knight) {
            return p + 5;
        } else if (p >= white_hand_lance) {
            return p + 4;
        } else if (p >= black_hand_lance) {
            return p + 3;
        } else if (p >= white_hand_pawn) {
            return p + 2;
        } else if (p >= black_hand_pawn) {
            return p + 1;
        }
    };

 問題はパラメータ自体の読み込み部分であり、どうもパラメータがおかしくなっているようだった。やねうら王を見てもAperyを見てもよくわからなかったが、Noviceのevaluate.cxxを見ることで解決した。KPPT型評価関数はKKPにもT部分を持っているということを知らず、KKPの方をただのint16_tで読み込もうとしていた。実際にはKKPにも手番ボーナスがあるため、型としてはstd::array<int16_t, 2>とするのが正しいようだ。

 現在の評価パラメータとApery(WCWC28)の評価パラメータを今の探索部にそれぞれ読み込み、自己対局を行った。現在の評価パラメータから見た対局結果が次のようになる。

対局数 勝利数 引き分け数 敗北数
2323 67 7 2249

 引き分けを0.5勝として勝率は約3.0%、Eloレート差にして601.8であった。

 予想よりも勝率が高い(0%になると思っていた)が、本来KKPTとして調整されている値の手番なしの方だけを抜き出して使用しているのでAperyパラメータの正しい棋力が発揮されていないことは確実である。今後は海底もKKPT_KPPT型に変更する。再学習が必要になるため検証はまたしばらく後になる。

 勝率が高い他の原因としては多様性を確保するために初手6手をランダムにしたため思考開始時点で形勢に差がついていることが原因かもしれない。しかし勝っていた棋譜をいくらか眺めると必ずしもそうではないようだった。

 コメントに残しておいた読み筋などを見るとAperyの評価パラメータを読み込んだ方に中終盤で致命的な読み抜けが発生しており、探索部に問題があるのではないかとも思われる。読み抜けが発生した局面を新規に検討させたところ実際に指された悪手は出てこなかったため、置換表に問題があるのではないかという疑いが生まれた。次回は置換表について検討する。

 以下が読み込み部分の全体となる。

template<typename T>
inline void EvalParams<T>::readAperyFile(std::string path) {
    constexpr int64_t AperyPieceStateNum = 1548;
    using KKPType = std::array<int16_t, 2>;
    using KPPType = std::array<int16_t, 2>;
    std::vector<KKPType> kkp_tmp(SqNum * SqNum * AperyPieceStateNum);
    std::vector<KPPType> kppt_tmp(SqNum * AperyPieceStateNum * AperyPieceStateNum);
    std::string kkp_file_name = path + "KKP.bin";
    std::string kppt_file_name = path + "KPP.bin";
    std::ifstream kkp_ifs(kkp_file_name, std::ios::binary);
    if (kkp_ifs.fail()) {
        std::cerr << kkp_file_name + " cannot open." << std::endl;
        clear();
        return;
    }
    std::ifstream kppt_ifs(kppt_file_name, std::ios::binary);
    if (kppt_ifs.fail()) {
        std::cerr << kppt_file_name + " cannot open." << std::endl;
        clear();
        return;
    }
    kkp_ifs.read(reinterpret_cast<char*>(kkp_tmp.data()), sizeof(KKPType) * kkp_tmp.size());
    kppt_ifs.read(reinterpret_cast<char*>(kppt_tmp.data()), sizeof(KPPType) * kppt_tmp.size());

    for (int64_t k1 = 0; k1 < SqNum; k1++) {
        for (int64_t p1 = 0; p1 < PieceStateNum; p1++) {
            int64_t apery_p1 = changeToAperyPieceState(p1);
            for (int64_t k2 = 0; k2 < SqNum; k2++) {
                auto key = k1 * SqNum * AperyPieceStateNum + k2 * AperyPieceStateNum + apery_p1;
                auto val = kkp_tmp[key][0];
                kkp[k1][k2][p1] = val;
            }
            for (int64_t p2 = 0; p2 < PieceStateNum; p2++) {
                int64_t apery_p2 = changeToAperyPieceState(p2);
                auto key = k1 * AperyPieceStateNum * AperyPieceStateNum + apery_p1 * AperyPieceStateNum + apery_p2;
                auto val = kppt_tmp[key];
                kppt[k1][p1][p2][0] = val[0];
                kppt[k1][p1][p2][1] = val[1];
            }
        }
    }
}

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;
    }
}