■ [others]JAGSummerCamp11 Day2 
3.5時間だけ参加させてもらいました。
E:Entangled with Lottery
ゴールに近い側からスタートに向けて見ていって、prob_win[追加で線を引いた個数][何本目の縦棒か] でDPする。
たぶんJの次に簡単
F:Power of Power
場合分けゲー。
0と1が特殊なので別扱い。こいつらの累乗の結果を1にする制約の下でどう並べると辞書順最小になるかが肝。
2以上の数字については、ソートして小さいものを下に置くのが最適（証明してないけど）。ただしソートした結果が 2,...2,3 の場合のみ、最後2つを入れ替える。
- 0が偶数個の場合
- 0,0,...0,1,1... の順で並べて最後にくっつける
- 0が奇数個の場合
- 1が0個の場合
- 0,0,..0 だけで並べてしまうとこの部分が0になってしまうので、2以上の部分から一番小さいもの（Mとする）を1つ犠牲にして 0,0,..0,M,0 の順で並べると1になってくれる。これを最後にくっつける
- 1が1個以上の場合
- 0,0,...1,0,1,1... の順で並べて最後にくっつける
- 1が0個の場合
H:Rectangular Stamps
時間切れで解いてないけど、bitDPでやればできそうな気がする。ただし状態の更新が面倒そう
I:Starting Line
あえてニンジンを取っておいた方が結果が良くなることはないので、スピードアップの効果が切れたとき、またはこれ以上ニンジンを持てなくなったときに、ニンジンをさっさと食いまくるのを実装する。
自分はWAでえらくはまってしまったけど皆さんずいぶんすんなり通しているようで素晴らしい
J:Tiles are Colorful
取れなくなるまでループ回して調べる。
アルファベットは26種類しかないので余裕
E:
import java.util.Arrays; import java.util.Scanner; public class E { static Scanner sc = new Scanner(System.in); static int H, N, P, M, K; public static void main(String[] args) throws Exception { H = sc.nextInt(); N = sc.nextInt(); P = sc.nextInt() - 1; M = sc.nextInt(); K = sc.nextInt(); int[] bridge = new int[H]; Arrays.fill(bridge, -1); for (int i = 0; i < M; ++i) { int A = sc.nextInt() - 1; int B = sc.nextInt() - 1; bridge[A] = B; } double[][] prob = new double[K + 1][N]; prob[0][P] = 1.0; int rest = H - M; for (int i = H - 1; i >= 0; --i) { if (bridge[i] != -1) { for (int j = 0; j <= K; ++j) { swap(prob[j], bridge[i], bridge[i] + 1); } } else { double[][] next = new double[K + 1][N]; for (int j = 0; j <= K; ++j) { double select = 1.0 * (K - j) / rest; for (int k = 0; k < N; ++k) { next[j][k] += prob[j][k] * (1.0 - select); } if (j < K) { next[j + 1][0] += select * (prob[j][0] * (N - 2) / (N - 1) + prob[j][1] / (N - 1)); for (int k = 1; k < N - 1; ++k) { next[j + 1][k] += select * (prob[j][k] * (N - 3) / (N - 1) + prob[j][k - 1] / (N - 1) + prob[j][k + 1] / (N - 1)); } next[j + 1][N - 1] += select * (prob[j][N - 1] * (N - 2) / (N - 1) + prob[j][N - 2] / (N - 1)); } } prob = next; --rest; } } double ans = 0; for (int i = 0; i < N; ++i) { ans = Math.max(ans, prob[K][i]); } System.out.println(ans); } static void swap(double[] a, int i, int j) { double tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }
F:
import java.util.Arrays; import java.util.Scanner; public class F { static Scanner sc = new Scanner(System.in); static int N; public static void main(String[] args) throws Exception { N = sc.nextInt(); int[] a = new int[N]; for (int i = 0; i < N; ++i) { a[i] = sc.nextInt(); } Arrays.sort(a); int cur = 0; while (cur < a.length && a[cur] == 0) { ++cur; } int c0 = cur; while (cur < a.length && a[cur] == 1) { ++cur; } int c1 = cur - c0; if (c0 % 2 == 0) { solve(cur, a); for (int i = 0; i < c0; ++i) { System.out.println(0); } for (int i = 0; i < c1; ++i) { System.out.println(1); } } else { if (c1 > 0) { solve(cur, a); for (int i = 0; i < c0 - 1; ++i) { System.out.println(0); } System.out.println(1); System.out.println(0); for (int i = 0; i < c1 - 1; ++i) { System.out.println(1); } } else { solve(cur + 1, a); for (int i = 0; i < c0 - 1; ++i) { System.out.println(0); } if (cur < a.length) { System.out.println(a[cur]); } System.out.println(0); } } } static void solve(int pos, int[] a) { if (pos <= a.length - 2 && a[a.length - 2] == 2 && a[a.length - 1] == 3) { for (int i = pos; i < a.length - 2; ++i) { System.out.println(2); } System.out.println(3); System.out.println(2); return; } for (int i = pos; i < a.length; ++i) { System.out.println(a[i]); } } }
I:
import java.util.Scanner; public class I { static Scanner sc = new Scanner(System.in); static int N, K; static double T, L, U, V; public static void main(String[] args) throws Exception { N = sc.nextInt(); K = sc.nextInt(); T = sc.nextInt(); U = sc.nextInt(); V = sc.nextInt(); L = sc.nextInt(); double[] D = new double[N + 1]; for (int i = 0; i < N; ++i) { D[i] = sc.nextInt(); } D[N] = L; int carrot = 0; double sep = D[0]; double time = D[0] / U; for (int i = 0; i < N; ++i) { ++carrot; if (sep >= D[i + 1]) { time += (D[i + 1] - D[i]) / V; if (carrot > K) { sep = D[i] + V * T; carrot = K; } continue; } if (carrot > K) { sep = D[i] + V * T; carrot = K; } int need = (int) Math.ceil((D[i + 1] - sep) / (T * V)); if (need > carrot) { time += (sep - D[i]) / V + T * carrot + (D[i + 1] - sep - V * T * carrot) / U; sep = D[i + 1]; carrot = 0; } else { time += (D[i + 1] - D[i]) / V; sep += V * T * need; carrot -= need; } } System.out.println(time); } }
J:
import java.util.Scanner; public class J { static Scanner sc = new Scanner(System.in); static char[][] field; public static void main(String[] args) throws Exception { int M = sc.nextInt(); int N = sc.nextInt(); int[][] r = new int[26][2]; int[][] c = new int[26][2]; boolean[] found = new boolean[26]; field = new char[M][N]; for (int i = 0; i < M; ++i) { String line = sc.next(); field[i] = line.toCharArray(); for (int j = 0; j < N; ++j) { if (field[i][j] != '.') { int idx = field[i][j] - 'A'; r[idx][found[idx] ? 1 : 0] = i; c[idx][found[idx] ? 1 : 0] = j; found[idx] = true; } } } int count = 0; while (true) { boolean removed = false; for (int i = 0; i < 26; ++i) { if (!found[i]) continue; if (reachable(r[i][0], c[i][0], r[i][1], c[i][1])) { removed = true; field[r[i][0]][c[i][0]] = '.'; field[r[i][1]][c[i][1]] = '.'; found[i] = false; break; } } if (!removed) { break; } ++count; } System.out.println(count * 2); } static boolean reachable(int r1, int c1, int r2, int c2) { if (Math.abs(r2 - r1) + Math.abs(c2 - c1) == 1) return false; boolean ok = true; for (int i = r1 + 1; i < r2; ++i) { if (field[i][c1] != '.') { ok = false; break; } } for (int i = Math.min(c1, c2) + 1; i < Math.max(c1, c2); ++i) { if (field[r2][i] != '.') { ok = false; break; } } if (field[r2][c1] != '.' && field[r2][c1] != field[r1][c1]) { ok = false; } if (ok) return true; ok = true; for (int i = Math.min(c1, c2) + 1; i < Math.max(c1, c2); ++i) { if (field[r1][i] != '.') { ok = false; break; } } for (int i = r1 + 1; i < r2; ++i) { if (field[i][c2] != '.') { ok = false; break; } } if (field[r1][c2] != '.' && field[r1][c2] != field[r1][c1]) { ok = false; } if (ok) return true; return false; } }
