TopCoder SRM 693

久々にオンタイムで参加したのでメモ。

Div1 Easy(250): BiconnectedDiv1

グラフが2-edge-connectedであるとは、グラフ中のどの１辺を削除しても、任意の頂点の組の間にパスが存在することを言う。

n頂点のグラフGが2-edge-connectedを満たしたまま、辺をいくつか削除して、辺のコストの合計を最小にしたときの値を求めよ。

• 3 <= n <= 100
• 頂点G[i] と G[i+1] はコスト w1[i] でつながっている。
• 頂点G[i] と G[i+2] はコスト w2[i] でつながっている。
• 0 <= w1[i], w2[i] <= 10000

考えたこと

どの辺を削除してもパスが存在するので、１つの辺のみにつながる頂点が存在してはいけないことが分かる。 なので、頂点に２つ以上の辺が繋がった状態になるように辺を削っていけばよい。

結果

Challenge Succeeded

x– (0.00pts) 1222→1224

レーティング落ちなくてよかった。。。

あとで

本番は繋がった状態を何パターン化に分けて計算したが、考慮漏れあり、、、 あとでちゃんとDPしたコード：

class BiconnectedDiv1 {
public:
    int minimize(vector <int> w1, vector <int> w2) {
        int n = w1.size() + 1;
        vi dp(n, 0);
        int total = 0;
        REP(i, n-1) {
            total += w1[i];
        }
        REP(i, n-2) {
            total += w2[i];
        }
        FOR(i, 2, n - 2) {
            dp[i] = dp[i - 1] + w1[i - 1];
            if (i > 2) {
                dp[i] = max(dp[i], dp[i - 2] + w2[i - 2]);
            }
        }

        return total - dp[n-2];
    }
};