2012-10-28

■ [others]CodeSprint3 23:03

https://cs3.interviewstreet.com/challenges/dashboard/#problems

ちょうどスケジュールあいてたので出てみた。

Webサイトの挙動が謎すぎて面白かった。問題は普通。

嘘解法（未証明解法）も混じってるけどいちおう満点

Exchange

交換できる関係をグラフと考えて、連結している範囲内は自由に交換できるので貪欲に

ワーシャルフロイドで推移閉包出す部分をミスってて2WA

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int K = sc.nextInt();
		int[] P = new int[K];
		for (int i = 0; i < K; ++i) {
			P[i] = sc.nextInt();
		}
		boolean[][] g = new boolean[K][K];
		for (int i = 0; i < K; ++i) {
			String line = sc.next();
			for (int j = 0; j < K; ++j) {
				g[i][j] = line.charAt(j) == 'Y';
			}
			g[i][i] = true;
		}
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < K; ++j) {
				for (int k = 0; k < K; ++k) {
					if (!g[j][k] && g[j][i] && g[i][k]) {
						g[j][k] = g[k][j] = true;
					}
				}
			}
		}
		int[] ans = new int[K];
		boolean[] used = new boolean[K];
		for (int i = 0; i < K; ++i) {
			if (used[i]) continue;
			ArrayList pos = new ArrayList();
			ArrayList elem = new ArrayList();
			for (int j = 0; j < K; ++j) {
				if (g[i][j]) {
					used[j] = true;
					pos.add(j);
					elem.add(P[j]);
				}
			}
			Collections.sort(elem);
			for (int j = 0; j < elem.size(); ++j) {
				ans[pos.get(j)] = elem.get(j);
			}
		}
		for (int i = 0; i < K - 1; ++i) {
			System.out.print(ans[i] + " ");
		}
		System.out.println(ans[K - 1]);
	}

}

Power Outage I

まず最小全域森を作って、長い辺から順に(K-連結成分の数)個取り除くと良い（ちゃんと証明してない）

入力で1回TLE

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {

	//	static Scanner sc = new Scanner(System.in);
	static Reader input = new BufferedReader(new InputStreamReader(System.in));
	static int N, K;
	static ArrayList edges = new ArrayList();

	public static void main(String[] args) throws Exception {
		int T = nextInt();
		for (int i = 0; i < T; ++i) {
			N = nextInt();
			edges.clear();
			int M = nextInt();
			K = nextInt();
			for (int j = 0; j < M; ++j) {
				int a = nextInt() - 1;
				int b = nextInt() - 1;
				int c = nextInt();
				edges.add(new Edge(a, b, c));
			}
			System.out.println(solve());
		}
	}

	static String solve() {
		if (K >= N) return "0";
		UnionFind uf = new UnionFind(N);
		Collections.sort(edges);
		int connect = 0;
		int sum = 0;
		for (int i = 0; i < edges.size(); ++i) {
			Edge e = edges.get(i);
			if (!uf.find(e.from, e.to)) {
				uf.union(e.from, e.to);
				sum += e.cost;
				connect++;
				if (connect == N - K) break;
			}
		}
		if (connect == N - K) {
			return sum + "";
		} else {
			return "Impossible!";
		}
	}

	static class UnionFind {
		int[] set;

		UnionFind(int n) {
			set = new int[n];
			Arrays.fill(set, -1);
		}

		void union(int a, int b) {
			int rtA = root(a);
			int rtb = root(b);
			if (rtA == rtb) {
				return;
			}
			set[rtA] += set[rtb];
			set[rtb] = rtA;
		}

		boolean find(int a, int b) {
			return root(a) == root(b);
		}

		int root(int a) {
			if (set[a] < 0) {
				return a;
			} else {
				set[a] = root(set[a]);
				return set[a];
			}
		}

		int size(int a) {
			return -set[root(a)];
		}
	}

	static class Edge implements Comparable {
		int from, to, cost;

		Edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}

		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	static int nextInt() throws Exception {
		int sign = 1;
		int b = input.read();
		while ((b < '0' || '9' < b) && b != '-' && b != '+') {
			b = input.read();
		}
		if (b == '-') {
			sign = -1;
			b = input.read();
		} else if (b == '+') {
			b = input.read();
		}
		int ret = b - '0';
		while (true) {
			b = input.read();
			if (b < '0' || '9' < b) return ret * sign;
			ret *= 10;
			ret += b - '0';
		}
	}

}

Power Outage II

タイブレーク問題。

スコア関数がゆとり仕様だったので、最も総コストが下がる位置に発電機を置いていく、というてきとーなgreedyで出してみたら満点になった

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

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[][] dist;
	static int[] L, G;
	static final int INF = 1 << 29;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		int M = sc.nextInt();
		dist = new int[N][N];
		for (int[] a : dist) {
			Arrays.fill(a, INF);
		}
		for (int i = 0; i < N; ++i) {
			dist[i][i] = 0;
		}
		for (int i = 0; i < M; ++i) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			dist[a][b] = dist[b][a] = sc.nextInt();
		}
		L = new int[N];
		for (int i = 0; i < N; ++i) {
			L[i] = sc.nextInt();
		}
		G = new int[N];
		for (int i = 0; i < N; ++i) {
			G[i] = sc.nextInt();
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					if (dist[j][k] > dist[j][i] + dist[i][k]) {
						dist[j][k] = dist[k][j] = dist[j][i] + dist[i][k];
					}
				}
			}
		}
		solve();
	}

	static void solve() {
		long[] cost = new long[N];
		int[] to = new int[N];
		Arrays.fill(cost, 1L << 50);
		Arrays.fill(to, -1);
		for (int i = 0; i < N; ++i) {
			long minDiff = 0;
			int minI = -1;
			for (int j = 0; j < N; ++j) {
				if (to[j] == j) continue;
				long prev = 0;
				long next = G[j];
				for (int k = 0; k < N; ++k) {
					if (dist[j][k] == INF) continue;
					prev += cost[k];
					next += Math.min(cost[k], (long) L[k] * dist[j][k]);
				}
				long diff = next - prev;
				if (diff < minDiff) {
					minDiff = diff;
					minI = j;
				}
			}
			if (minDiff < 0) {
				for (int j = 0; j < N; ++j) {
					if (dist[j][minI] == INF) continue;
					long newCost = (long) L[j] * dist[j][minI];
					if (newCost < cost[j]) {
						cost[j] = newCost;
						to[j] = minI;
					}
				}
			}
		}

		ArrayList post = new ArrayList();
		for (int i = 0; i < N; ++i) {
			if (to[i] == i) {
				post.add(i);
			}
		}
		System.out.println(post.size());
		for (int i = 0; i < post.size(); ++i) {
			System.out.print((post.get(i) + 1) + " ");
		}
		System.out.println();
		for (int i = 0; i < N; ++i) {
			System.out.print((to[i] + 1) + " ");
		}
		System.out.println();
	}

}

nCr

142857=3^3*11*13*37なので、nCrをmod 27, mod 11, mod 13, mod 37でそれぞれ求めて中国剰余定理で合成すれば良い

素数を法としてnCrを求める方法は蟻本に載っているけど、mod 27がそのままでは無理でやっかい

英語版Wikipediaでウィルソンの定理のページを見ると、mod P だけではなくて mod P^N の場合への拡張が載っていたのでこれを使って求めた

http://en.wikipedia.org/wiki/Wilson%27s_theorem#Gauss.27s_generalization

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.Reader;
import java.math.BigInteger;

public class Solution {

	static Reader input = new BufferedReader(new InputStreamReader(System.in));
	static final int MOD = 142857;
	static int N, R;
	static final int[] ps = new int[] { 3, 11, 13, 37 };
	static final int[] bases = new int[] { 27, 11, 13, 37 };
	static final int[][] factTables = new int[ps.length][];

	public static void main(String[] args) throws Exception {
		for (int i = 0; i < bases.length; ++i) {
			factTables[i] = new int[bases[i]];
			int f = 1;
			for (int j = 0; j < bases[i]; ++j) {
				factTables[i][j] = f;
				if ((j + 1) % ps[i] != 0) {
					f *= j + 1;
				}
				f %= bases[i];
			}
		}
		StringBuilder sb = new StringBuilder();
		int T = nextInt();
		for (int i = 0; i < T; ++i) {
			N = nextInt();
			R = nextInt();
			if (R > N / 2) R = N - R;
			sb.append(solve() + "\n");
		}
		System.out.print(sb);
	}

	static int solve() {
		int[][] res = new int[4][];
		for (int i = 0; i < 4; ++i) {
			res[i] = modComb(N, R, bases[i], ps[i], factTables[i]);
		}
		int[] rem = new int[4];
		for (int i = 0; i < 4; ++i) {
			rem[i] = res[i][0];
		}
		return chineseRemainder(bases, rem);
	}

	// returns {remainder, power of p} 
	static int[] modFact(int n, int p, int base, int[] factTable) {
		if (n == 0) return new int[] { 1, 0 };
		int[] ret = modFact(n / base, p, base, factTable);
		ret[1] += n / base;
		if (n / p % 2 == 0) {
			ret[0] = ret[0] * factTable[n % p] % p;
		} else {
			ret[0] = ret[0] * (p - factTable[n % p]) % p;
		}
		return ret;
	}

	static int[] modComb(int n, int r, int p, int base, int[] factTable) {
		int[] a1 = modFact(n, p, base, factTable);
		int[] a2 = modFact(r, p, base, factTable);
		int[] a3 = modFact(n - r, p, base, factTable);
		int pow = a1[1] - a2[1] - a3[1];
		int rem;
		if (base == 3) {
			if (pow >= 3) {
				rem = 0;
			} else {
				rem = a1[0] * inv(a2[0] * a3[0] % p, p) % p;
				for (int i = 0; i < pow; ++i) {
					rem *= base;
				}
				rem %= p;
			}
		} else {
			if (pow > 0) {
				rem = 0;
			} else {
				rem = a1[0] * inv(a2[0] * a3[0] % p, p) % p;
			}
		}
		return new int[] { rem, pow };
	}

	static int solveNaive() {
		int[] count = new int[ps.length];
		for (int i = 0; i < ps.length; ++i) {
			count[i] = count(N, ps[i]) - count(N - R, ps[i]) - count(R, ps[i]);
		}
		if (count[0] >= 3 && count[1] >= 1 && count[2] >= 1 && count[3] >= 1) return 0;
		BigInteger v = BigInteger.ONE;
		for (int i = 0; i < R; ++i) {
			v = v.multiply(BigInteger.valueOf(N - i)).divide(BigInteger.valueOf(i + 1));
		}
		return v.remainder(BigInteger.valueOf(MOD)).intValue();
	}

	static int chineseRemainder(int[] mod, int[] rem) {
		int m1 = mod[0];
		int r1 = rem[0];
		for (int i = 1; i < mod.length; ++i) {
			int m2 = mod[i];
			int r2 = rem[i];
			r1 = chineseRemainder(m1, r1, m2, r2);
			m1 *= m2;
		}
		return r1;
	}

	static int chineseRemainder(int m1, int r1, int m2, int r2) {
		int A = ((r2 - r1) % m2 + m2) * inv(m1, m2) % m2;
		return (A * m1 + r1) % (m1 * m2);
	}

	static int calc(int prime, int mod) {
		long ret = 1;
		for (int i = 0; i < R; ++i) {
			int num = N - i;
			while (num % prime == 0) {
				num /= prime;
			}
			ret *= num;
			int den = i + 1;
			while (den % prime == 0) {
				den /= prime;
			}
			ret *= inv(den, mod);
			ret %= mod;
		}
		return (int) ret;
	}

	static int inv(int v, int mod) {
		return pow(v, totient(mod) - 1, mod);
	}

	static int totient(int v) {
		int ret = v;
		for (int i = 0; i < ps.length && v > 1; ++i) {
			if (v % ps[i] == 0) {
				v /= ps[i];
				while (v % ps[i] == 0) {
					v /= ps[i];
				}
				ret /= ps[i];
				ret *= (ps[i] - 1);
			}
		}
		return ret;
	}

	static int pow(int v, int p, int mod) {
		if (p == 0) return 1;
		int ret = pow(v, p / 2, mod);
		ret *= ret;
		ret %= mod;
		if (p % 2 == 1) {
			ret *= v;
			ret %= mod;
		}
		return ret;
	}

	static int count(int n, int d) {
		int ret = 0;
		while (n > 0) {
			ret += n / d;
			n /= d;
		}
		return ret;
	}

	static int nextInt() throws Exception {
		int sign = 1;
		int b = input.read();
		while ((b < '0' || '9' < b) && b != '-' && b != '+') {
			b = input.read();
		}
		if (b == '-') {
			sign = -1;
			b = input.read();
		} else if (b == '+') {
			b = input.read();
		}
		int ret = b - '0';
		while (true) {
			b = input.read();
			if (b < '0' || '9' < b) return ret * sign;
			ret *= 10;
			ret += b - '0';
		}
	}

}

Bowling

最後のフレームだけ別扱いしてDP

マルチケースなのでDPテーブルは前計算しておく

オーバーフローで2WA

import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int MOD = 1000000007;

	public static void main(String[] args) throws Exception {
		long[][][] dp = new long[101][4][3101]; // 2次元目は前のフレームからの影響 {0,0}, {0,1}, {0,2}, {1,2}
		dp[0][0][0] = 1;
		for (int i = 0; i < 100; ++i) {
			for (int j = 0; j <= i * 30; ++j) {
				// strike
				add(dp[i + 1][2], j + 10, dp[i][0][j]);
				add(dp[i + 1][2], j + 20, dp[i][1][j]);
				add(dp[i + 1][3], j + 20, dp[i][2][j]);
				add(dp[i + 1][3], j + 30, dp[i][3][j]);

				// spare
				for (int k = 0; k <= 9; ++k) {
					add(dp[i + 1][1], j + 10, dp[i][0][j]);
					add(dp[i + 1][1], j + 10 + k, dp[i][1][j]);
					add(dp[i + 1][1], j + 20, dp[i][2][j]);
					add(dp[i + 1][1], j + 20 + k, dp[i][3][j]);
				}

				// open
				for (int k = 0; k <= 9; ++k) {
					for (int l = 0; l + k < 10; ++l) {
						add(dp[i + 1][0], j + k + l, dp[i][0][j]);
						add(dp[i + 1][0], j + k + l + k, dp[i][1][j]);
						add(dp[i + 1][0], j + k + l + k + l, dp[i][2][j]);
						add(dp[i + 1][0], j + k + l + k + k + l, dp[i][3][j]);
					}
				}
			}
		}
		int[][] dp2 = new int[4][61];
		for (int i = 0; i <= 10; ++i) {
			int rest = i == 10 ? 10 : 10 - i;
			boolean extra = i == 10;
			for (int j = 0; j <= rest; ++j) {
				int rest2 = rest - j;
				if (rest2 == 0) {
					extra = true;
					rest2 = 10;
				}
				if (extra) {
					for (int k = 0; k <= rest2; ++k) {
						dp2[0][i + j + k]++;
						dp2[1][i + j + k + i]++;
						dp2[2][i + j + k + i + j]++;
						dp2[3][i + j + k + i + j + i]++;
					}
				} else {
					dp2[0][i + j]++;
					dp2[1][i + j + i]++;
					dp2[2][i + j + i + j]++;
					dp2[3][i + j + i + j + i]++;
				}
			}
		}
		int T = sc.nextInt();
		for (int i = 0; i < T; ++i) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			long ans = 0;
			for (int j = M; j >= Math.max(0, M - 60); --j) {
				for (int k = 0; k < dp[0].length; ++k) {
					ans += dp[N - 1][k][j] * dp2[k][M - j];
					ans %= MOD;
				}
			}
			System.out.println(ans);
		}
	}

	static void add(long[] a, int index, long amount) {
		a[index] += amount;
		if (a[index] >= MOD) a[index] -= MOD;
	}

}

Concatenated Palindrome

manacherのアルゴリズムとか使わないといかんのかなぁと思いつつ、とりあえずTLE解を出しておくか、と提出してみたら通った

新しい文字列を作りまくらない、という程度の効率化はしている

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

public class Solution {

	static Scanner sc = new Scanner(System.in);
	static int N, M;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		M = sc.nextInt();
		String[] strs = new String[N];
		SubStr[] forward = new SubStr[N];
		SubStr[] backward = new SubStr[N];
		for (int i = 0; i < N; ++i) {
			strs[i] = sc.next();
			forward[i] = new SubStr(strs[i], 0, true, M);
			forward[i].index = i;
			backward[i] = new SubStr(strs[i], M - 1, false, M);
			backward[i].index = i;
		}
		Arrays.sort(forward);
		Arrays.sort(backward);
		System.out.println(Math.max(solve(forward, backward), solve(backward, forward)));
	}

	static int solve(SubStr[] pre, SubStr[] suf) {
		int ans = 0;
		for (int i = 0; i < N; ++i) {
			int pos = Arrays.binarySearch(pre, suf[i]);
			int lo, hi;
			if (pos < 0) {
				lo = -pos - 2;
				hi = -pos - 1;
			} else {
				lo = hi = pos;
			}
			if (lo >= 0 && pre[lo].index == suf[i].index) {
				--lo;
			}
			if (hi < N && pre[hi].index == suf[i].index) {
				++hi;
			}
			if (lo < 0) lo = 0;
			if (hi >= N) hi = N - 1;
			for (int j = lo; j <= hi; ++j) {
				if (pre[j].index == suf[i].index) continue;
				ans = Math.max(ans, count(suf[i], pre[j]));
			}
		}
		return ans;
	}

	static int count(SubStr s1, SubStr s2) {
		int pos = countMatch(s1, s2);
		SubStr[] sa = new SubStr[M - pos];
		for (int i = pos; i < M; ++i) {
			sa[i - pos] = new SubStr(s1.str, s1.start + i * s1.diff, s1.diff == -1, i - pos + 1);
		}
		SubStr rest = new SubStr(s1.str, s1.start + pos * s1.diff, s1.diff == 1, M - pos);
		for (int i = sa.length - 1; i >= 0; --i) {
			if (countMatch(rest, sa[i]) == sa[i].len) {
				return pos * 2 + sa[i].len;
			}
		}
		return pos * 2;
	}

	static int countMatch(SubStr s1, SubStr s2) {
		int i = 0;
		for (; i < Math.min(s1.len, s2.len); ++i) {
			if (s1.str.charAt(s1.start + i * s1.diff) != s2.str.charAt(s2.start + i * s2.diff)) return i;
		}
		return i;
	}

	static class SubStr implements Comparable {
		String str;
		int start;
		int diff;
		int len;
		int index;

		SubStr(String s, int start, boolean forward, int len) {
			this.str = s;
			this.start = start;
			this.diff = forward ? 1 : -1;
			this.len = len;
		}

		public int compareTo(SubStr o) {
			int p1 = this.start;
			int p2 = o.start;
			for (int i = 0; i < Math.min(this.len, o.len); ++i) {
				if (this.str.charAt(p1) < o.str.charAt(p2)) {
					return -1;
				}
				if (this.str.charAt(p1) > o.str.charAt(p2)) {
					return 1;
				}
				p1 += this.diff;
				p2 += o.diff;
			}
			if (this.len < o.len) return -1;
			if (this.len > o.len) return 1;
			return 0;
		}
	}

}

Random number generator

まずAC

import java.util.Scanner;

public class Solution {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int N = sc.nextInt();
		for (int i = 0; i < N; ++i) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int C = sc.nextInt();
			solve(Math.min(A, B), Math.max(A, B), C);
		}
	}

	static void solve(long A, long B, long C) {
		if (A + B <= C) {
			System.out.println("1/1");
			return;
		}
		long num, den;
		if (C < A) {
			num = C * C;
			den = 2 * A * B;
		} else if (C < B) {
			num = 2 * C - A;
			den = 2 * B;
		} else {
			num = 2 * C * (B + A) - A * A - B * B - C * C;
			den = 2 * A * B;
		}
		long gcd = gcd(num, den);
		System.out.println(num / gcd + "/" + den / gcd);
	}

	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

}