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