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

Facebook Hacker Cup 2014 Round 1 Solutions

結果

Hacker CupのRound 1がありました。
無事通過できてた！よかった。

Editorialが出たので、Editorialの内容を忠実に（？）に実装してみました。

Labelmaker

Editorial解、賢い。。

普通のa進数の場合、 x₂ x₁ x₀（a進数表記） = a²x₂ + ax₁ + x₀（10進数表記）となりますが、今回の問題の場合は

x₂ x₁ x_{0　（a進数表記）}
= a²x₂ + ax₁ + x₀ + a² + a + 1
= a²(x₂ + 1) + a(x₁ + 1) + (x₀ + 1)　（10進数表記）

のようになることを利用して解きます。a² + a + 1の意味はそれぞれ、長さ2の数の総数、長さ1の数の総数、0-baseじゃなくて1-baseです。

import java.util.Scanner;

public class A {
    private Scanner in = new Scanner(System.in);
    
    private void solve() {
        String s = in.next();
        long n = in.nextLong();
        int len = s.length();

        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(s.charAt((int) (--n % len)));
            n /= len;
        }
        
        System.out.println(sb.reverse().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 A().run();
    }
}

Coins Game

本番中はO(N)解で解きましたが、EditorialのようにO(1)で解けます。これが一番難しかったです。

import java.util.Scanner;

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

    private void solve() {
        long n = in.nextLong();
        long k = in.nextLong();
        long c = in.nextLong();
        
        long height = (c + n - 1) / n;
        if (k >= height * n)
            System.out.println(c);
        else
            System.out.println(c + n - k / height);
    }

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

AAAAAA

本番中は、backwardに進むセグメントの始点と終点を全部試すというO(N^3)解で解きました。が、状態数を
(セルの位置、どの方向から来たか？、backward移動は使ってしまったか？)
としてDPするとO(N^2)で解けます。

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

public class C {
    private Scanner in = new Scanner(System.in);
    int[][][][] dp = new int[500][500][4][2];
    int r, c;
    char[][] bd = new char[500][500];
    final int DOWN = 0, RIGHT = 1, UP = 2, LEFT = 3;
    
    private int rec(int x, int y, int dir, int used) {
        if (x < 0 || x >= r) return 0;
        if (y < 0 || y >= c) return 0;
        if (bd[x][y] == '#') return 0;
        
        if (dp[x][y][dir][used] != -1)
            return dp[x][y][dir][used];
        
        int ret = 0;
        if (used == 1) {
            ret = Math.max(ret, 1+rec(x+1, y, DOWN, 1)); 
            ret = Math.max(ret, 1+rec(x, y+1, RIGHT, 1)); 
        } else {
            switch (dir) {
            case DOWN:
                ret = Math.max(ret, 1+rec(x+1, y, DOWN, 0)); 
                ret = Math.max(ret, 1+rec(x, y+1, RIGHT, 0));
                ret = Math.max(ret, 1+rec(x, y-1, LEFT, 0));
                break;
            case RIGHT:
                ret = Math.max(ret, 1+rec(x+1, y, DOWN, 0)); 
                ret = Math.max(ret, 1+rec(x, y+1, RIGHT, 0)); 
                ret = Math.max(ret, 1+rec(x-1, y, UP, 0));
                break;
            case UP:
                ret = Math.max(ret, 1+rec(x-1, y, UP, 0));
                ret = Math.max(ret, 1+rec(x, y+1, RIGHT, 1)); 
                break;
            case LEFT:
                ret = Math.max(ret, 1+rec(x, y-1, LEFT, 0));
                ret = Math.max(ret, 1+rec(x+1, y, DOWN, 1)); 
                break;
            default:
                throw new IllegalArgumentException();
            }
        }

        return dp[x][y][dir][used] = ret;
    }
    
    private void solve() {
        r = in.nextInt();
        c = in.nextInt();
        for (int i = 0; i < r; i++) {
            String line = in.next();
            bd[i] = line.toCharArray();
        }
        
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                for (int k = 0; k < 4; k++)
                    Arrays.fill(dp[i][j][k], -1);

        System.out.println(rec(0, 0, 0, 0));
    }

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

Preventing Alzheimer's

本番中はpruning付きのDFSで解きました。
これがビットDPで解けるとは考えもしませんでしたが、いろいろ分析していくとDPで解けます。
bitmaskでは、50以下の素数しか管理していません。例えば、53の場合は106のみをブロックしてしまいますが、106使うなら53使った方がいい（A[i]の初期値は50以下）ので、53使えばいいじゃん。というふうになって、p * 3 > 150となるような素数pについてはその合成数を使うよりは素数pを使った方が必ずお得ということになります。

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

public class D {
    private Scanner in = new Scanner(System.in);
    
    final int INF = 99999999;
    int primes[] = {
            2, 3, 5, 7, 11, 13, 17, 19, 
            23, 29, 31, 37, 41, 43, 47
    };
    int largePrimes[] = {
            53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
            101, 103, 107, 109, 113, 127, 131, 137, 139, 149
    };
    int[][][] dp = new int[21][1<<15][21];
    int[] factors = new int[150];
    
    private void init() {
        for (int i = 0; i < 150; i++) {
            for (int j = 0; j < largePrimes.length; j++) {
                if (i > 0 && i % largePrimes[j] == 0)
                    factors[i] = -1;
            }
            
            // consider largePrimes' multiples separately.
            if (factors[i] == -1)
                continue;
            
            for (int j = 0; j < primes.length; j++) {
                if (i % primes[j] == 0)
                    factors[i] |= 1 << j;
            }
        }
    }
    
    private void solve() {
        int N = in.nextInt();
        int K = in.nextInt();
        
        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = in.nextInt();
        
        int ret = 0;
        // any problem comes down to a problem where K = 1
        for (int i = 0; i < N; i++) {
            int tmp = A[i];
            A[i] = (A[i] + K - 1)/K;
            ret += A[i] * K - tmp;
        }
        
        // base case
        for (int i = 0; i < 1<<15; i++)
            Arrays.fill(dp[N][i], 0);
        
        // dp transition
        for (int pos = N-1; pos >= 0; pos--) {
            for (int mask = 0; mask < 1<<15; mask++) {
                for (int largeP = 0; largeP <= 20; largeP++) {
                    dp[pos][mask][largeP] = INF;
                    
                    // try small numbers
                    for (int i = A[pos]; i < 150; i++) {
                        if ((mask & factors[i]) != 0 || factors[i] == -1)
                            continue;
                        dp[pos][mask][largeP] = Math.min(dp[pos][mask][largeP], 
                                i - A[pos] + dp[pos+1][mask | factors[i]][largeP]);
                    }
                    
                    // A[] is sorted and largePrimes[largeP] is always greater than A[pos].
                    // So just use the smallest possible largePrime.
                    if (largeP < 20) {
                        dp[pos][mask][largeP] = Math.min(dp[pos][mask][largeP], 
                                largePrimes[largeP] - A[pos] + dp[pos+1][mask][largeP+1]);
                    }
                }
            }
        }
        
        ret += dp[0][0][0] * K;
        System.out.println(ret);
    }

    public void run() {
        init();
        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 D().run();
    }
}