Eclipse CDT環境設定

Eclipse CDTの環境設定メモ。
既存のソースをEclipseのプロジェクトに入れてコンパイル/実行が出来るようにするまでの作業メモ。

Unresolved inclusion: を解決する

プロジェクト右クリック - Properties - C/C++ General - Path and Symbols - Includesタブ - LanguesでGNU Cを選択 - AddでIncludeしたいファイルのパスを追加。

 標準関数のインクルードパスがどこにあるかを知りたいときは、適当なtest.cを作って

gcc -v -E test.c

とすれば、

(省略)
#include <...> の探索はここから始まります:
 /usr/lib/gcc/i686-linux-gnu/4.6/include
 /usr/local/include
 /usr/lib/gcc/i686-linux-gnu/4.6/include-fixed
 /usr/include/i386-linux-gnu
 /usr/include
(省略)

のように表示されるので、これらをAddで追加すればよい。

math libraryをリンクする

プロジェクト右クリック - Properties - C/C++ Build - Settings - Tool Settingsタブ - GCC C Linker - Libraries - +ボタン - "m"と入力（ダブルクオーテーションの中身のみ入力） - OK

なんかいろいろ警告が出るのを消す

警告なのに赤線で出てきてやな感じだったので、-wオプションでコンパイルすることにした。

プロジェクト右クリック - Properties - C/C++ Build - Settings - Tool Settingsタブ - GCC C Compiler - Warnings - inhibit all warningsのみチェック - OK

Facebook Hacker Cup 2014 Round 2 Solutions

Editorialが出たので復習した。Hacker CupのEditorialはとても丁寧でわかりやすいなー。
Sample sourceがなかったので、実装してみた。

Magic Pairs

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class A {
    private Scanner in = new Scanner(System.in);
    int N, M;
    long[] X, Y;

    void read() {
        N = in.nextInt();
        M = in.nextInt();

        X = new long[N];
        Y = new long[M];

        long x1 = in.nextLong();
        long a1 = in.nextLong();
        long b1 = in.nextLong();
        long c1 = in.nextLong();
        long r1 = in.nextLong();
        long x2 = in.nextLong();
        long a2 = in.nextLong();
        long b2 = in.nextLong();
        long c2 = in.nextLong();
        long r2 = in.nextLong();

        X[0] = x1;
        Y[0] = x2;

        for (int i = 1; i < Math.max(N, M); i++) {
            if (i < N)
                X[i] = (a1 * X[(i - 1) % N] + b1 * Y[(i - 1) % M] + c1) % r1;
            if (i < M)
                Y[i] = (a2 * X[(i - 1) % N] + b2 * Y[(i - 1) % M] + c2) % r2;
        }
    }

    private void solve() {
        read();
        long ret = 0;

        Set<Long> yOnly = new HashSet<Long>();
        Set<Long> Both = new HashSet<Long>();

        int j = 0;
        for (int i = 0; i < X.length; i++) {
            if (yOnly.contains(X[i])) {
                yOnly.remove(X[i]);
                Both.add(X[i]);
            }
            if (!Both.contains(X[i])) {
                while (j < Y.length) {
                    if (Y[j] == X[i]) {
                        Both.add(X[i]);
                        break;
                    }
                    if (!Both.contains(Y[j]))
                        yOnly.add(Y[j]);
                    ++j;
                }
            }
            if (j >= Y.length) break;
            if (yOnly.size() > 0) continue;
            
            int ni = i, nj = j;
            while (ni < X.length && Both.contains(X[ni])) ++ni;
            while (nj < Y.length && Both.contains(Y[nj])) ++nj;
            
            ret += (long)(ni - i) * (nj - j);
            i = --ni;
            j = nj;
        }

        System.out.println(ret);
    }

    public void run() {
        int T = in.nextInt();
        for (int testcase = 1; testcase <= T; testcase++) {
            System.err.printf("Solving Case #%d...\n", testcase);
            System.out.printf("Case #%d: ", testcase);
            solve();
        }
    }

    public static void main(String[] args) {
        new A().run();
    }
}

Hold'em Numbers

import java.util.Arrays;
import java.util.Scanner;

public class B {
    private Scanner in = new Scanner(System.in);

    boolean conflict(int a1, int b1, int a2, int b2) {
        if (a1 == a2 || a1 == b2) return true;
        if (b1 == a2 || b1 == b2) return true;
        return false;
    }

    int comp(int a1, int b1, int a2, int b2) {
        if (a1 + b1 != a2 + b2) return (a1 + b1) - (a2 + b2);
        return Math.max(a1, b1) - Math.max(a2, b2);
    }

    long countWorse(int a, int b, int N) {
        long[] hands = new long[N + 1];
        long totalHands = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (conflict(a, b, i, j)) continue;
                if (comp(a, b, i, j) <= 0) continue;
                ++totalHands;
                ++hands[i];
                ++hands[j];
            }
        }

        long ret = 0;
        for (int c = 1; c <= N; c++) {
            for (int d = c + 1; d <= N; d++) {
                if (conflict(a, b, c, d)) continue;
                if (comp(a, b, c, d) <= 0) continue;
                for (int e = 1; e <= N; e++) {
                    for (int f = e + 1; f <= N; f++) {
                        if (conflict(a, b, e, f)) continue;
                        if (conflict(c, d, e, f)) continue;
                        if (comp(a, b, e, f) <= 0) continue;
                        long cnt = totalHands - (hands[c] + hands[d] + hands[e] + hands[f]);
                        if (comp(a, b, c, d) > 0) ++cnt;
                        if (comp(a, b, c, e) > 0) ++cnt;
                        if (comp(a, b, c, f) > 0) ++cnt;
                        if (comp(a, b, d, e) > 0) ++cnt;
                        if (comp(a, b, d, f) > 0) ++cnt;
                        if (comp(a, b, e, f) > 0) ++cnt;
                        ret += cnt;
                    }
                }
            }
        }

        return ret;
    }

    class Hand implements Comparable<Hand> {
        int x;
        int y;

        Hand(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Hand o) {
            if (x + y != o.x + o.y)
                return x + y - (o.x + o.y);
            return Math.max(x, y) - Math.max(o.x, o.y);
        }
    }

    private void solve() {
        int N = in.nextInt();
        int H = in.nextInt();

        Hand[] hands = new Hand[N * (N - 1) / 2];
        int k = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                hands[k++] = new Hand(i, j);
            }
        }
        Arrays.sort(hands);

        int hi = hands.length - 1;
        int lo = -1;
        long total = (long)(N - 2) * (N - 3) * (N - 4) * (N - 5) * (N - 6) * (N - 7) / 8;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            long cnt = countWorse(hands[mid].x, hands[mid].y, N);
            if (4 * cnt > total)
                hi = mid;
            else
                lo = mid;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < H; i++) {
            int C1 = in.nextInt();
            int C2 = in.nextInt();

            int pos = 0;
            while (pos < hands.length) {
               if (hands[pos].x == C1 && hands[pos].y == C2)
                    break;
                if (hands[pos].x == C2 && hands[pos].y == C1)
                    break;
                ++pos;
            }

            if (pos >= hi)
                sb.append('B');
            else
                sb.append('F');
        }

        System.out.println(sb.toString());
    }

    public void run() {
        int T = in.nextInt();
        for (int testcase = 1; testcase <= T; testcase++) {
            System.err.printf("Solving Case #%d...\n", testcase);
            System.out.printf("Case #%d: ", testcase);
            solve();
        }
    }

    public static void main(String[] args) {
        new B().run();
    }
}

Ski Resort Planning

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class C {
    private Scanner in = new Scanner(System.in);
    private static final long MOD =  1000000007;
    int N;
    int[] par;
    List<Integer>[] children;
    int[][] dp;
    long[] two;
    
    {
        dp = new int[5000][5000];
        two = new long[5001];
        two[0] = 1;
        for (int i = 1; i <= 5000; i++)
            two[i] = 2 * two[i-1] % MOD;
    }
    
    @SuppressWarnings("unchecked")
    private void read() {
        N = in.nextInt();
        par = new int[N];
        children = new List[N];
        for (int i = 0; i < N; i++)
            children[i] = new ArrayList<Integer>();

        par[0] = -1;
        for (int i = 1; i < N; i++) {
            par[i] = in.nextInt();
            children[par[i]].add(i);
        }
    }

    private void solve() {
        read();

        for (int v = N-1; v >= 0; v--) {
            for (int k = 0; k < N; k++) {
                dp[v][k] = 0;
                if (v < k)
                    ++dp[v][k];
                for (int w : children[v])
                    dp[v][k] += dp[w][k];
            }
        }
        
        long ret = 1;
        for (int i = 1; i < N; i++) {
            int cnt = 1;
            for (int j : children[par[i]])
                cnt += dp[j][i];
            long add = two[cnt] - 1;
            for (int j : children[par[i]])
                add -= two[(int) dp[j][i]] - 1;
            add = (add % MOD + MOD) % MOD;
            ret = ret * add % MOD;
        }
        System.out.println(ret);
    }

    public void run() {
        int T = in.nextInt();
        for (int testcase = 1; testcase <= T; testcase++) {
            System.err.printf("Solving Case #%d...\n", testcase);
            System.out.printf("Case #%d: ", testcase);
            solve();
        }
    }

    public static void main(String[] args) {
        new C().run();
    }
}

ペロン＝フロベニウスの定理でページランク

　最近「ペロン=フロベニウスの定理」というのをたまたま見かけた。これを使うとページランクの計算が高速化されそうだったので、実験してみた。

ペロン=フロベニウスの定理とは？

成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である[1]。
らしい。証明はまだ読んでないけど、時間のあるとき読む。

ページランクにどう使うか？

もっとも基本的なページランクのモデルを考えます。
 
　上式のように、あるノードのrankはそのノードにリンクを張っているノードの重み付き和とします。これは行列で表現すると、v = Avとなるようなv（つまりAの固有ベクトル）を求めればよいことになります。ただし、Aはグラフの隣接行列です。

　ここまでは昔から知っていましたが、いくつか疑問点がありました。

• |v| = 10^5程度でも行列Aのサイズが10^10となってしまい、簡単には計算できないのではないか？（そのままだとメモリに乗らないし。）行列が疎であることを利用した効率的な計算方法はないのか？
• 考えているグラフは有向グラフだけど正の実数の固有値は存在するのか？（無向グラフの場合は、隣接行列が対称行列なので実数の固有値が存在するし、トレースが0なので正の固有値が存在するんだけど。）

　ペロン=フロベニウスの定理を見たとき、「これか！」とピーンと来ました。

この定理を利用すると、行列Aの最大固有値は正の実数になります。

また、「任意のベクトルに線型写像を施すとそのベクトルは最大固有値に対応する固有ベクトル方向に近づいていく。」という性質を使うと、最大固有値に対応する固有ベクトルは簡単に計算することができます。さらにさらに、この方法で固有ベクトルを計算する場合は、グラフを隣接行列でもつ必要はなく、隣接リストでOKなので空間計算量もO(E)ですみます。

ソースコード

簡単な例題で正しく計算できていることを確認していますが、バグがあるかもしれません。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct edge {
    int from;
    double cost;
};

typedef vector<vector<edge> > adjList;

const double EPS = 1e-9;

/*
 * perform a linear transform nxt := A * cur.
 * notice that A is represented as an adjacency list.
 */
void transform(const adjList &edgesTo, const vector<double> &cur, vector<double> &nxt) {
    int N = cur.size();
    
    double abs = 0;
    for (int i = 0; i < N; i++) {
        nxt[i] = 0;
        for (int j = 0; j < edgesTo[i].size(); j++) {
            const edge &e = edgesTo[i][j];
            nxt[i] += e.cost * cur[e.from];
        }
        abs += nxt[i] * nxt[i];
    }
    
    // normalize a vector nxt
    abs = sqrt(abs);
    for (int i = 0; i < N; i++)
        nxt[i] /= abs;
}

/*
 * calc the distance between two vectors v and w.
 */
double dist(const vector<double> &v, const vector<double> &w) {
    double d = 0;
    for (int i = 0; i < v.size(); i++)
        d += (v[i]-w[i]) * (v[i]-w[i]);
    d = sqrt(d);
    return d;
}

/*
 * display a vector's elements.
 */
void disp(const vector<double> &v) {
    for (int i = 0; i < v.size(); i++)
        cout << i << ": " << v[i] << endl;
}

int main(int argc, char **argv) {
    int N;
    cin >> N;
    adjList edgesTo = adjList(N);

    for (int i = 0; i < N; i++) {
        int deg;
        cin >> deg;
        for (int j = 0; j < deg; j++) {
            int to;
            cin >> to;
            edgesTo[to].push_back((edge){i, 1./deg});
        }
    }

    vector<double> v[2];
    v[0] = vector<double>(N, 1/sqrt(N));
    v[1] = vector<double>(N);

    for (int i = 0; dist(v[0], v[1]) > EPS; i++) {
        transform(edgesTo, v[i&1], v[(i+1)&1]);
        cerr << i << " th iteration: dist = " << dist(v[0], v[1]) << endl;
    }
    
    // page rank values
    cout << "################################################" << endl;
    cout << "page rank values are below:" << endl;
    cout << "################################################" << endl;
    disp(v[0]);

    return 0;
}

入力のフォーマットは以下のようなかんじ。

3      # ノード数
2 1 2  # v0の出次数は2。v1とv2にリンクしている。
1 0    # v1の出次数は1。v0にリンクしている。
1 1    # v2の出次数は1。v1にリンクしている。

ノード数が10^5, 各ノードの出次数を10^2とした場合、6秒くらいで結果が出た。予想してたより固有ベクトルの収束が速かった。これ使ってSNSのソーシャルグラフを使って実験とかしてみると面白そうな気がする。

references

[1] ペロン＝フロベニウスの定理 - Wikipedia