Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

競技プログラミング練習記 No.22【ABC146-D練習】

初回 -> はじめに

ABC146 - D : Coloring Edges on Treeを解きました。
前は難しくて解けなかった問題です。

問題 時間 アルゴリズム 実行時間
D 75min 深さ優先探索 115ms

ABC146のA-C問題はこちら
競技プログラミング練習記 No.11【ABC146練習】

D - Coloring Edges on Tree

using P = pair<int, int>;

bool visited[200005];
int max_color = 0;
vector<int> ans(200005, 0);
vector< vector<int> > edge(200005, vector<int>());
map< P, int > edges_pair;

void dfs(int now, int parent_color)
{
    if (visited[now]) return;
    visited[now] = true;

    int color = (parent_color + 1) % max_color;
    for(const auto& next : edge[now])
    {
        if (visited[next]) continue;
        P p = ((now < next) ? P(now, next) : P(next, now));
        ans[edges_pair[p]] = color + 1;
        dfs(next, color);
        color = (color + 1) % max_color;
    }
}

void solve()
{
    fill(visited, visited + 200005, false);
    int n, a ,b;
    cin >> n;

    for(int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        a--; b--;
        edge[a].emplace_back(b);
        edge[b].emplace_back(a);
        if (a > b) swap(a, b);
        edges_pair[P(a, b)] = i;
    }

    for(const auto& e : edge)
    {
        max_color = max(max_color, (int)e.size());
    }
    cout << max_color << endl;

    dfs(0, max_color - 1);
    for(int i = 0; i < n - 1; ++i)
    {
        cout << ans[i] << endl;
    }
}

使用する色については誘導問題みたいなものです。
頂点の最大次数がそのまま色の種類になりますね。

木について、頂点ではなく枝を探索します。BFSでもDFSでもいいのですが、今回はDFSを使いました。
DFSをしながら、親の方向にある枝とは違う色で自分を塗ります。

今回は時間との戦いでした。
dfs() 内の
P p = ((now < next) ? P(now, next) : P(next, now));
ans[edges_pair[p]] = color + 1;
で、枝から入力時の枝番号へ変換しているのですが、初めはvectorfindを使っていました。
vectorfindO(N)かかります。それでやられました。
プログラムにあるように、mapを使えばO(log N)で変換でき、時間も間に合いました。

ちなみに、map平衡二分探索木です。
要素のアクセス・要素の検索・要素の挿入・要素の削除がどれもO(log N)で実行されます。
vectorの場合はアクセスがO(1)で非常に高速ですが、要素の検索にO(N)かかり非常に低速です。

今回は過去に解けていなかった問題を解きました。
ABC170-E : Smart Infants が似た問題で解けていないので、次はこれを解きたいですね。

以上です。ありがとうございました。

gummie
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away