SRM 627 Div1 Med, GraphInversions

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13275

N 頂点, N 辺 (3 <= N <= 1000) の連結な無向グラフが与えられる. 各頂点は属性として値 v_i (1 <= v_i <= 1000) を持つ. 長さ K 以上の全ての単純路について, それぞれ v_i の系列で表した時に, 最も小さい転倒数 (inversion) を求めよ.

解法

それぞれの頂点に対して, 深さ K まで dfs する. 探索の計算量は N² におさまる.
dfs しながら同時に, inversion を BIT で求める.
O(N² log(N)).

実装

#define loop(n, i) for(int i=0;i<n;i++)

class GraphInversions
{
public:
    vector<int> G[1001];
    vector<int> V;
    int used[1001] = {};
    BIT *bit;

    int getMinimumInversions (vector <int> A, vector <int> B, vector <int> V, int K)
    {
        int N = A.size();
        this->V = V;
        loop (N, i) {
            G[A[i]].push_back(B[i]);
            G[B[i]].push_back(A[i]);
        }

        int ans = INF;
        loop (N, i) {
            bit = new BIT(1001);
            ans = min(ans, dfs(i, K));
            delete bit;
        }
        if (ans == INF) return -1;
        return ans;
    }

    int dfs(int i, int k) {
        if (used[i]) return INF;

        int crr = bit->sum(1000) - bit->sum(V[i]);
        if (k == 1) return crr;

        used[i] = 1;
        bit->add(V[i], 1);
        int rest = INF;
        for (int j : G[i]) if (!used[j]) {
            rest = min(rest, dfs(j, k-1));
        }
        used[i] = 0;
        bit->add(V[i], -1);

        if (rest == INF) return INF;
        return rest+crr;
    }
};

Binary Indexed Tree (BIT, Fenwick Tree)

概要

整数列 に対して, 以下のクエリを O(log(n)) で実現するデータ構造.

1. : を求める
2. : に を加える

特徴

Segment Tree の機能縮小版で, 実装がむちゃくちゃ簡単.

構造

深さ log(n) の二分木であり, 各ノードは以下の法則で値を保持する.

1. 葉:
2. 葉の親:
3. 葉の親の親: [tex: a_1+a_2+a_3+a_4,\ a_9+a{10}+a{11}+a_{12}, \dots]

クエリ処理は, 葉から根へ高々 log(n) 回の計算で完了する.
例えば, は で求められる.

用途

転倒数 (inversion) を求めるなど

実装に関する補足

木を配列としてうまく持つことで実装がものすごく簡易になる. 詳細は下記ページを参照.

TopCoder Algorithm Tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
わかりやすいスライド: http://hos.ac/slides/20140319_bit.pdf

実装

class BIT
{
public:
    vector<int> bit;
    int M;

    BIT(int M):
        bit(vector<int>(M+1, 0)), M(M) {}

    int sum(int i) {
        if (!i) return 0;
        return bit[i] + sum(i-(i&-i));
    }

    void add(int i, int x) {
        if (i > M) return;
        bit[i] += x;
        add(i+(i&-i), x);
    }
};

暗唱のポイント

• 1-indexed
• (i&-i) で rightmost set bit だけ取り出せる
• 木 について, sum は重ならない方向(左), add は重なる方向(右)

互いに素な3つ組の総数

問題

http://www.codechef.com/LTIME13/problems/COPRIME3
整数 N (0 < N < 10⁵) と, N 個の整数 a_0, a_1, ..., a_[n-1] (0 < a_i < 10⁶) が与えられる.
0 < i < j < k <= N として, a_i, a_j, a_k が互いに素となるような (i, j, k) の個数を出力せよ.
(制限時間1秒)

解答

gcd(a_i, a_j, a_k) = m なる (i, j, k) の個数に対する動的計画法で解く.
dp[m] は gcd() = m なる (i, j, k) の個数を表すとして, dp[10⁶] から順に計算していく.
dp[1] が答えとなる.
計算量オーダーは, a_i の最大値を M (=10⁶) として, O(Mlog(M)).

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
const int MAX = 1000000;

int main(int argc, char const* argv[])
{
    int N; cin >> N;
    int cnt[MAX+10] = {};
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        cnt[a]++;
    }

    vector<ll> dp(MAX+10);
    for (int i = MAX; i; i--) {
        // 入力値のうち i で割り切れるものの個数
        int mults = 0;
        for (int j = i; j <= MAX; j += i) mults += cnt[j];

        // multsから3つ選ぶ組み合わせ (mults C 3)
        dp[i] = (ll)mults*(mults-1)*(mults-2)/6;

        // dp[i*2], dp[i*3], ... を除く
        for (int j = i*2; j <= MAX; j += i) dp[i] -= dp[j];
    }

    cout << dp[1] << endl;
    return 0;
}

この方法だと簡単にnつ組に拡張できる.