SoundHound Inc. Programming Contest 2018 -Masters Tournament-：E - + Graph

問題

https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e

考え方

考えていたこと

グラフは連結であるから、ある頂点のコストを決め打ちすると頂点と辺の関係から他の頂点のコストが一意に決まることが分かる。なのでまずは頂点 0 のコストを 0 として考えることとする。

そのとき頂点のコストを 0 から 1 に変化させると、偶数長の頂点は + の変化をして、奇数長の頂点は - の変化をすることが分かる。

がサンプル1のようにある頂点が偶数長にも奇数長にもなりうる場合にどうしていいかわからず...

解説見た

グラフが二部グラフであるかそうでないかが重要。二部グラフの場合、各頂点の偶奇は一意に決まるので、頂点 0 のコストを 0 できめうちして各頂点のコストを計算した後に、それぞれの頂点が 0 以下にならないように初期値の幅を調整すれば良い。このときの初期値の候補が求める場合の数である。

二部グラフではない場合は、実は場合の数は高々 1 通りになる。ある頂点について、奇数長でのコストを a - t とし、偶数長でのコストを b + t とすると、これらが一致するときの t は \displaystyle \frac{|a-b|}{2} で定まるためである。サンプル1の場合、以下の図のイメージ。グラフが2面あることをイメージすると理解しやすかった。

f:id:d_tutuz:20190221211350j:plain:w300

よって \displaystyle t=\frac{|a-b|}{2} として頂点 0 から再度 dfs で各頂点のコストを求めたときにそれぞれの頂点のコストが 0 以下にならなければ解は 1 そうでなければ 0 となる。

Submission #4339483 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

実装テク

偶奇分の二回グラフを計算すると実装が楽。kmjpさんの実装を参考にした。

    // [初期コスト][偶奇][頂点] = コスト
    cost = new long[2][2][n];

    void dfs(int id, int st, int cur, long v) {
        if (cost[id][st][cur] == LINF) {
            cost[id][st][cur] = v;
            for (P p : g[cur]) {
                dfs(id, st^1, p.t, p.c - v);
            }
        }
    }

どこに着目して考察するべきだったか

頂点 0 からの長さの偶奇が重要である。また与えられたグラフが二部グラフであるかどうかがポイントであった。

何がバグっていたか

得た知見(典型ポイント)

  • 偶奇性から二部グラフを考える

類題

参考