■ [others]OUPC2012 
http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=OUPC2012
短い問題文よいですね。日本語であっても
- A
- D
- とりあえずBigIntegerでRationalクラス作って投げてみる
- 予想通りTLE
- G
- まず回文にできるかどうかを判定する
- あとは全体の半分だけを考えればよくて基本的な組み合わせの問題
- 64bit整数で良かったみたいだけど、細かいこと考えるのが面倒でBigIntegerで
- AC
- L
- K
- E
- 一瞬ラグランジュの未定乗数法使うのかと思ったけど0<=xi<=1の制約があるので違う
- とりあえず自明なケースはよくて、w<0,v<0のもの（「負の商品」）とw>0,v>0のもの（「正の商品」）をどう扱うか
- まず状況を単純にして正の商品だけがある場合を考えると、価値/重さの効率が良いやつから順に重さ合計がWになるまでgreedyに使えばよい
- あと負の商品については、現在使おうとしている正の商品よりも価値/重さの効率が悪かったら、その負の商品を使って価値を犠牲にして重さを減らしてやることで、その分正の商品を入れる余地ができて全体の価値は上がる
- とこんな感じでgreedyに使ってゆく
- 数回のWAののちAC
- 最初に間違った考え方で書いていたコードを変形していったので何度もミスを出してしまった
- D
- B
- 読んだだけ
- 普通にやったらN^2になってだめで、どうするんだろう、空間分割とかやるのかなあ
- と思ったくらいで後回しにしていて考える時間がなかった
- C
- きっと約数関係でグラフにして二部マッチングだろうなあ、N=100というところからも
- というくらいまでは考えたけど、どうすれば二部マッチングが適用できる形になるのかわからなかった
- 蟻本が手元になかったのが痛い
- F
- 読んだだけ
- H
- 読んだだけ
- 木にしてDPかなあ、くらい
- 戦略としてはDじゃなくてこっちを考えておくべきだった
- I
- 読んだだけ
- Lunaticです
- J
- 読んだだけ
- とりあえず座標圧縮は必要だろう、そのあとどうすれば、というところまで
- 5AC/12問
- 3位/40人・チーム
- A
import java.util.Arrays; import java.util.Scanner; public class A { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String A = sc.next(); String B = sc.next(); int N = A.length(); int[] as = new int[N]; int[] bs = new int[N]; for (int i = 0; i < N; ++i) { as[i] = A.charAt(i) - '0'; } for (int i = 0; i < B.length(); ++i) { bs[N - B.length() + i] = B.charAt(i) - '0'; } int K = sc.nextInt(); int[][][] dp = new int[N + 1][K + 1][2]; for (int[][] aa : dp) { for (int[] a : aa) { Arrays.fill(a, Integer.MIN_VALUE); } } int base = 1; dp[0][0][0] = 0; for (int i = 1; i <= N; ++i, base *= 10) { if (as[N - i] >= bs[N - i]) { for (int j = 0; j <= K; ++j) { dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][0] + base * (as[N - i] - bs[N - i])); } } else { for (int j = 0; j <= K; ++j) { dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][0] + base * (10 + as[N - i] - bs[N - i])); if (j != 0) { dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j - 1][0] + base * (10 + as[N - i] - bs[N - i])); } } } if (as[N - i] - 1 >= bs[N - i]) { for (int j = 0; j <= K; ++j) { dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j][1] + base * (as[N - i] - 1 - bs[N - i])); } } else { for (int j = 0; j <= K; ++j) { dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][1] + base * (10 + as[N - i] - 1 - bs[N - i])); if (j != 0) { dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j - 1][1] + base * (10 + as[N - i] - 1 - bs[N - i])); } } } } int ans = 0; for (int i = 0; i <= K; ++i) { ans = Math.max(ans, dp[N][i][0]); ans = Math.max(ans, dp[N][i][1]); } System.out.println(ans); } }
- E
import java.math.BigDecimal; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class E { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int N = sc.nextInt(); double W = sc.nextInt(); int[] w = new int[N]; int[] v = new int[N]; double ans = 0; for (int i = 0; i < N; ++i) { w[i] = Integer.parseInt(sc.next()); v[i] = Integer.parseInt(sc.next()); if (w[i] <= 0 && v[i] >= 0) { ans += v[i]; W -= w[i]; } } ArrayListadd = new ArrayList (); ArrayList sub = new ArrayList (); for (int i = 0; i < N; ++i) { if (w[i] > 0 && v[i] > 0) { add.add(new Product(w[i], v[i])); } else if (w[i] < 0 && v[i] < 0) { sub.add(new Product(w[i], v[i])); } } Collections.sort(add); Collections.sort(sub); int addI = add.size() - 1; double addX = 1.0; int subI = 0; double subX = 1.0; while (addI >= 0) { // System.out.println(W + " " + ans + " " + addI + " " + addX + " " + subI + " " + subX); double needW = add.get(addI).w * addX; if (W == 0) { if (subI >= sub.size() || add.get(addI).e() < sub.get(subI).e()) break; double feedW = Math.abs(sub.get(subI).w) * subX; if (feedW < needW) { W += feedW; ans += sub.get(subI).v * subX; ++subI; subX = 1.0; } else { double difX = needW / Math.abs(sub.get(subI).w); W = needW; ans += sub.get(subI).v * difX; subX -= difX; } // System.out.println(" " + W + " " + ans + " " + addI + " " + addX + " " + subI + " " + subX); } if (needW > W) { ans += add.get(addI).e() * W; addX -= W / add.get(addI).w; W = 0; } else { ans += add.get(addI).e() * needW; W -= needW; --addI; addX = 1.0; } } System.out.println(new BigDecimal(ans).toPlainString()); } static class Product implements Comparable { int w, v; Product(int w, int v) { this.w = w; this.v = v; } double e() { return 1.0 * this.v / this.w; } public int compareTo(Product o) { return this.v * o.w - this.w * o.v; } } }
- G
import java.math.BigInteger; import java.util.Scanner; public class G { static Scanner sc = new Scanner(System.in); static long solve() { char[] s = sc.next().toCharArray(); int[] count = new int[26]; for (int i = 0; i < s.length; ++i) { ++count[s[i] - 'a']; } int odd = 0; for (int i = 0; i < count.length; ++i) { if (count[i] % 2 != 0) ++odd; } if (s.length % 2 == 0) { if (odd != 0) return 0; } else { if (odd != 1) return 0; } for (int i = 0; i < count.length; ++i) { count[i] /= 2; } BigInteger[] fact = new BigInteger[s.length / 2 + 1]; fact[0] = BigInteger.ONE; for (int i = 1; i < fact.length; ++i) { fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i)); } BigInteger ans = fact[s.length / 2]; for (int i = 0; i < count.length; ++i) { ans = ans.divide(fact[count[i]]); } return ans.longValue(); } public static void main(String[] args) { System.out.println(solve()); } }
- K
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class K { static final int MOD = 1000000007; static Scanner sc = new Scanner(System.in); static int N, M; static int[][] pos; static int[][] Y; static long solveCycle(ArrayList| list) { long ret = 0; // start = 0 long[][] dp = new long[list.size()][2]; dp[0][0] = 0; dp[0][1] = 1; for (int i = 1; i < list.size(); ++i) { if (list.get(i - 1).s == list.get(i).f) { dp[i][0] = dp[i - 1][1]; } else { dp[i][0] = dp[i - 1][0]; } dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } if (list.get(list.size() - 1).s == list.get(0).f) { ret += dp[list.size() - 1][0]; } else { ret += dp[list.size() - 1][1]; } // start = 1 dp = new long[list.size()][2]; dp[0][0] = 1; dp[0][1] = 1; for (int i = 1; i < list.size(); ++i) { if (list.get(i - 1).s == list.get(i).f) { dp[i][0] = dp[i - 1][1]; } else { dp[i][0] = dp[i - 1][0]; } dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } if (list.get(list.size() - 1).s == list.get(0).f) { ret += dp[list.size() - 1][1]; } else { ret += dp[list.size() - 1][0]; } return ret % MOD; } static long solveChain(ArrayList | list) { long[][] dp = new long[list.size()][2]; dp[0][0] = 1; dp[0][1] = 2; for (int i = 1; i < list.size(); ++i) { if (list.get(i - 1).s == list.get(i).f) { dp[i][0] = dp[i - 1][1]; } else { dp[i][0] = dp[i - 1][0]; } dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } return (dp[list.size() - 1][0] + dp[list.size() - 1][1]) % MOD; } public static void main(String[] args) { N = sc.nextInt(); M = sc.nextInt(); pos = new int[N + 1][2]; Y = new int[M][2]; for (int[] a : pos) { Arrays.fill(a, -1); } for (int i = 0; i < M; ++i) { Y[i][0] = sc.nextInt(); int x = Math.abs(Y[i][0]); if (pos[x][0] == -1) { pos[x][0] = i; } else { pos[x][1] = i; } Y[i][1] = sc.nextInt(); x = Math.abs(Y[i][1]); if (pos[x][0] == -1) { pos[x][0] = i; } else { pos[x][1] = i; } } boolean[] used = new boolean[M]; long ans = 1; for (int i = 0; i < M; ++i) { if (Math.abs(Y[i][0]) == Math.abs(Y[i][1])) { used[i] = true; if (Y[i][0] == -Y[i][1]) { ans *= 2; ans %= MOD; } } } while (true) { boolean update = false; for (int i = 0; i < M; ++i) { if (used[i]) continue; update = true; ArrayList | forward = new ArrayList | (); ArrayList | backward = new ArrayList | (); forward.add(new Cell(Y[i][0], Y[i][1])); used[i] = true; boolean cycle = false; int cur = i; int x = Math.abs(Y[cur][1]); while (true) { int otherI = pos[x][0] == cur ? 1 : 0; if (pos[x][otherI] == -1) break; cur = pos[x][otherI]; if (used[cur]) { cycle = true; break; } used[cur] = true; int inI = x == Math.abs(Y[cur][0]) ? 0 : 1; x = Math.abs(Y[cur][1 - inI]); forward.add(new Cell(Y[cur][inI], Y[cur][1 - inI])); } if (cycle) { ans *= solveCycle(forward); ans %= MOD; continue; } cur = i; x = Math.abs(Y[cur][0]); while (true) { int otherI = pos[x][0] == cur ? 1 : 0; if (pos[x][otherI] == -1) break; cur = pos[x][otherI]; if (used[cur]) { throw new RuntimeException(); } used[cur] = true; int inI = x == Math.abs(Y[cur][0]) ? 0 : 1; x = Math.abs(Y[cur][1 - inI]); backward.add(new Cell(Y[cur][1 - inI], Y[cur][inI])); } Collections.reverse(backward); backward.addAll(forward); ans *= solveChain(backward); ans %= MOD; } if (!update) break; } System.out.println(ans); } static class Cell { int f; int s; Cell(int f, int s) { this.f = f; this.s = s; } } } |
- L
import java.util.Arrays; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Scanner; public class L { static Scanner sc = new Scanner(System.in); static int N; static int[][] cost; static int solve() { PriorityQueueq = new PriorityQueue (); int[] ord = new int[N]; for (int i = 0; i < N; ++i) { ord[i] = i; } q.add(new State(0, ord)); HashSet visited = new HashSet (); int ans = 0; while (!q.isEmpty()) { State cur = q.poll(); if (visited.contains(cur)) continue; ans = cur.v; visited.add(cur); for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { swap(cur.ord, i, j); State next = new State(cur.v + cost[i][j], cur.ord); if (!visited.contains(next)) { q.add(next); } swap(cur.ord, i, j); } } } return ans; } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { N = sc.nextInt(); cost = new int[N][N]; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cost[i][j] = sc.nextInt(); } } System.out.println(solve()); } static class State implements Comparable { int v; int[] ord; State(int v, int[] o) { this.v = v; this.ord = o.clone(); } public int compareTo(State o) { return this.v - o.v; } public int hashCode() { return Arrays.hashCode(ord); } public boolean equals(Object obj) { if (this == obj) return true; State other = (State) obj; return Arrays.equals(ord, other.ord); } } }
