## 2013年12月18日水曜日

### 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;

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() {
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]);
}
if (!Both.contains(X[i])) {
while (j < Y.length) {
if (Y[j] == X[i]) {
break;
}
if (!Both.contains(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")
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();
}
}

private void solve() {

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