Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

問題概要

原文 → Problem - F1 - Codeforces

頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。

木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成できる辺の切り方は何通り存在するか？

解説

辺は 1 つだけしか取り除かないので、DFS をして解くことができます。

まず、適当に根を設定して根付き木として考えます。各頂点 に関して、「 を根とする部分木内に存在する 赤 / 青 の頂点数」を覚えておきます。これは DFS で可能です。

次に、ある辺を切ったときにできる 2 つの連結成分 について、 赤 / 青 がそれぞれいくつ含まれるかを各辺に対して計算します。これは、一方 () は DFS 時に得られた値を使えば良いですし、もう一方 () は全体から の情報を引くことで得られます。

どちらの連結成分に関しても、どちらか一方のみの色が含まれている場合、それは条件を満たす辺のひとつです。

ソースコード

const int S = 300000;
int cntR[S+10], cntB[S+10], col[S+10];
int ans;
vector<int> G[S+10];

void dfs(int cur, int par=-1) {
    if(col[cur] == 1) cntR[cur]++;
    if(col[cur] == 2) cntB[cur]++;
    for(auto to : G[cur]) {
        if(to == par) continue;
        dfs(to, cur);
        cntR[cur] += cntR[to];
        cntB[cur] += cntB[to];
    }
}

void dfs2(int cur, int par=-1, int root=0) {
    for(auto to : G[cur]) {
        if(to == par) continue;
        dfs2(to, cur);
        int R1 = cntR[to], B1 = cntB[to];
        int R2 = cntR[root] - R1, B2 = cntB[root] - B1;

        bool ok = true;
        ok &= (R1 == 0 or B1 == 0);
        ok &= (R2 == 0 or B2 == 0);
        ans += ok;
    }
}

signed main() {
    int N; scanf("%lld", &N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &col[i]);
    }

    for(int i=0; i<N-1; i++) {
        int a, b; scanf("%lld%lld", &a, &b);
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(0);
    dfs2(0);

    cout << ans << endl;
    return 0;
}

four-t practice 2019 #04

2019 年 3 月 2 日 (土) に 2014 Tehran Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。今回は環境構築の練習も兼ねて rsk0315 にコンパイルや実行のショートカット？を色々書いてもらい、TAB は前から、自分は後ろから見ていった。前の方に簡単な問題が多かったらしく、TAB が A, B をすぐ通してくれた。その後 F も rsk0315 が通してくれた。文字列系はだいたい rsk0315 に投げると解いてくれるのでたすかる。その間自分は後ろの問題の読解に苦戦していたので焦っていた。

I から K まで読んで、これ簡単な問題ひとつもなくないかと思いながら問題概要をいろいろ説明していく。伝えあっているうちに D が放置されていたことに気づき、みたらわりとわかりやすい最短路だったので解く AC (これ時間的にもったいなかったなあ) その後少々つまりながらも C も通る。

G は問題設定がなんかおもしろい。グラフである必要なくないかと思ったけどよく考えたら連結でないときに壊れることを TAB が指摘してくれたので助かった。これはすんなり通ってくれた。

簡単枠が全部片付いたので残りを全員で考えてみる。J は DP っぽいけどどう考えても無理なのでフローで考えたら方針ガチャに成功 (？) して、少々時間がきつそうな解法を思いついたが信じて提出。1WA したけど (すいません) 通る

I は幾何っぽいが、直感的にこうすればいいんじゃないかなあと思った解法を TAB に説明して書いてもらう。YesNo 問題だしサンプルがよわよわなので怖かったが一発で通る。幾何の方針だけ説明して実装を任せる悪い人になってしまった。残り 1 時間 45 分残して 8 完で、あと 3 問。

ここからかなりつらくて、主に E と H を考察していて H を実装したけど WA になってしまってそのまま終了。たぶん考察に漏れがある系のミスな気がするけど、復習しないとわからないですね・・・。

反省

2 桁チームが AC している問題を取りこぼすことは少なくなってきた気がする。まあ日本のアジア地区に比べて出題傾向もレベルも違う気がするのでアレなんですが・・・不可能枠の復習わりと不可能だけどやるしかないのかなあ

環境構築したら問題読解係の連携がちょっと崩れてしまったので、やっぱりこの辺含めて練習したほうが良さそう。ペナルティをすくなくしていきたい

やっぱり最後 1 時間で何もできなくなってしまいがちなのでそもそももう少し強くなりたいですね、おわり

Educational Codeforces Round 2 E: Lomsat gelral

問題概要

原文 → Problem - E - Codeforces

頂点からなる根付き木が与えられる。根は頂点 であり、木の各頂点には色 がついている。

各頂点 について、 を根とする部分木に存在する頂点の中で、塗られている個数が最も多い色を求め (タイもすべて数えるため複数ある場合がある)、色 id の合計を出力せよ。

解説

データ構造をマージする一般的なテク、通称「マージテク」を使って解くことを考えます。

現在の頂点 の情報と子 の情報をマージする際に、必ず「サイズが小さい方を大きい方に向けてマージする」ようにします。こうすることでマージ全体にかかる時間がならし 時間になります。map の計算量も含めて、 で処理可能です。

ソースコード

using Graph = vector< vector<int> >;

int N, col[100010], res[100010];
map<int, int> exist[100010];
map<int, int> sum[100010];

void solve(Graph &G, int cur, int par=-1) {
    exist[cur][ col[cur] ] = 1;
    sum[cur][1] = col[cur];
    for(auto to : G[cur]) {
        if(to == par) continue;
        solve(G, to, cur);

        // サイズを比較して、小さい方を大きい方に向けてマージ
        if(exist[cur].size() < exist[to].size()) {
            swap(exist[cur], exist[to]);
            swap(sum[cur], sum[to]);
        }

        // to を cur にマージ
        for(auto e : exist[to]) {
            int id, cnt; tie(id, cnt) = e;
            if(exist[cur].count(id)) {
                int cnt_ = exist[cur][id];
                cnt += cnt_;
                exist[cur][id] = cnt;
                sum[cur][cnt_] -= id;
                sum[cur][cnt ] += id;
            }
            else {
                exist[cur][id] = cnt;
                sum[cur][cnt] += id;
            }
        }
    }
    int ans = (--sum[cur].end())->second;
    res[cur] = ans;
}

signed main() {
    scanf("%lld", &N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &col[i]);
    }

    Graph G(N);
    for(int i=0; i<N-1; i++) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    solve(G, 0);
    for(int i=0; i<N; i++) {
        printf("%lld%c", res[i], " \n"[i+1 == N]);
    }
    return 0;
}