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();
    }
}