<-- home

AtCoder ARC 037

February 29, 2020

ARC037の自分用メモ

AtCoder 版！蟻本 (初級編)にC問題が類題として載っていたので解いた。

B-バウムテスト

無向グラフが与えられたとき、その部分グラフで木になっているものの数を答える問題。つまり連結成分で閉路を含まないものの個数を計算する。

連結成分の個数

頂点が訪問済みかどうかを表すリストを用意する。深さ優先探索を適当な頂点を始点として1度おこなうと、その頂点を含む連結成分に含まれるすべての頂点が訪問済みとなる。したがって、連結成分の個数を求めるには、すべての頂点について、それが訪問済みでなければ深さ優先探索をおこなう、という方法で深さ優先探索をおこなった回数を求めればいい。

閉路の検出

閉路が存在すれば、深さ優先探索をおこなっているとき、訪問済みの頂点を未使用の辺で辿ることができる。したがって、頂点が訪問済みかどうかを表すリストと、使用済みの辺のリストを用意して、深さ優先探索をおこない、それらを適宜更新することで、閉路を検出できる。実装では、辺が使用済みかどうかを隣接行列で表せばでその辺が使用済みかどうか調べられる。

実装

// テンプレ省略

#define MAX_N 100
#define MAX_M 4950
i64 N;  // |V|
i64 M;  // |E|
bool G[MAX_N][MAX_N];
bool E[MAX_N][MAX_N]; // edgeを使ったかどうか

bool visited[MAX_N]; // 行きがけ順で訪問済み

// false iff 閉路を検出したら
bool dfs(i64 u) {
    bool no_cycle = true;

    visited[u] = true;
    REP(v, N) {
        if (!G[u][v]) continue;

        if (visited[v] && !E[u][v]) {
            // 訪問済みの頂点に未使用の辺を使ってたどれる場合
            no_cycle = false;
            continue;
        }

        if (!visited[v]) {
            E[u][v] = true;
            E[v][u] = true;
            no_cycle &= dfs(v);
        }
    }

    return no_cycle;
}

void solve() {
    i64 cnt = 0; // 閉路を含まない連結成分の数

    // init
    fill(visited, visited + N, false);

    REP(s, N) {
        if (visited[s]) continue;
        cnt += dfs(s);
    }

    cout << cnt << endl;
}


int main() {
    cin >> N >> M;
    i64 u, v;
    REP(i, M) {
        cin >> u >> v;
        u--; v--; // 1-indexed to 0-indexed
        G[u][v] = true;
        G[v][u] = true;
        E[u][v] = false;
        E[v][u] = false;
    }

    solve();

    return 0;
}

C-億マス計算

個の値があって、K番目の数を求める問題。

という条件があるので、個の値をそれぞれ計算して、K番目の数を答えるという方法では当然時間が足りない。適当な数に対して、以下の数が何個あるのか効率的に数えられれば、二分探索でK番目の数を求められる。探索区間は

積()の個数を数える

しゃくとり法で数える。一応、二分探索(lower_bound)を使っても今回は間に合うはず。

例えば、 、が与えられたとき、以下の積の個数を数えたいとする。は以下のようになる。

A\B 6 5 4 3
2 12 10 8 6
3 18 15 12 9
4 24 20 16 12
5 30 25 20 15

緑色で表示された積が以下となっている。上の表で黒色と緑色の境界が、が大きくなるごとに、広義単調増加することに着目して以下の積の個数を効率的に数えるのがしゃくとり法。しゃくとり法の詳細については、このあたり(しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ)が詳しい。しゃくとり法を用いると、以下の積の個数をで数えられる。

実装

Aを昇順、Bを降順にソートしているが、別にBを昇順にソートしても同様の方法で解けるしそのあたりは好み。

// テンプレート省略

#define MAX_N 30000
i64 N, K;
i64 A[MAX_N];
i64 B[MAX_N];

i64 count(i64 x) {
    // x以下の積の個数を数える O(N)
    i64 cnt = 0;

    i64 a, b;
    i64 j = 0;
    REP(i, N) {
        a = A[i];
        while (j < N && (A[i] * B[j] > x)) {
            j++;
        }
        cnt += N - j;
    }

    return cnt;
}

void solve() {
    sort(A, A + N);
    sort(B, B + N, greater<i64>());

    i64 lb = 0;
    i64 ub = 1000000000000000001;
    while (ub - lb > 1) {
        i64 mid = (lb + ub) / 2;

        if (count(mid) >= K) ub = mid;
        else lb = mid;
    }

    cout << ub << endl;
}

int main() {
    cin >> N >> K;
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];

    solve();

    return 0;
}

類題