Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2012-03-20

[]OUPC2012 22:13 はてなブックマーク - OUPC2012 - TopCoderの学習のお時間

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=OUPC2012

短い問題文よいですね。日本語であっても


  • A
    • greedyに上の桁から選べば良い??
    • なんか違ってそう
    • まあDPやっとけばいいよね
    • AC
  • D
    • とりあえずBigIntegerでRationalクラス作って投げてみる
    • 予想通りTLE
  • G
    • まず回文にできるかどうかを判定する
    • あとは全体の半分だけを考えればよくて基本的な組み合わせの問題
    • 64bit整数で良かったみたいだけど、細かいこと考えるのが面倒でBigIntegerで
    • AC
  • L
    • ソートされた状態から逆向きにやると全部の状態を生成できて良い、というたまにあるパターン
    • 順列をノードにしてダイクストラする
    • AC
    • 速度的な対策は特別やっていない。リミット2秒のところ1.95秒とかだった。危ない
  • K
    • 「各変数は論理式に1回か2回だけ現れる」というのが明らかに見えている突破口で
    • ある変数の出現位置をたどっていくと、一列の鎖か輪っかのどちらかになる
    • あとはそれぞれDPして組み合わせ数を計算できる
    • ここまではすぐ見えたのでがんばって実装する
    • AC
    • けっこう実装重かったけど一発で通った。うれしい
  • E
    • 一瞬ラグランジュの未定乗数法使うのかと思ったけど0<=xi<=1の制約があるので違う
    • とりあえず自明なケースはよくて、w<0,v<0のもの(「負の商品」)とw>0,v>0のもの(「正の商品」)をどう扱うか
    • まず状況を単純にして正の商品だけがある場合を考えると、価値/重さの効率が良いやつから順に重さ合計がWになるまでgreedyに使えばよい
    • あと負の商品については、現在使おうとしている正の商品よりも価値/重さの効率が悪かったら、その負の商品を使って価値を犠牲にして重さを減らしてやることで、その分正の商品を入れる余地ができて全体の価値は上がる
    • とこんな感じでgreedyに使ってゆく
    • 数回のWAののちAC
    • 最初に間違った考え方で書いていたコードを変形していったので何度もミスを出してしまった
  • D
    • 逆から見ていって、ゴールから何倍になった状態かごとに足し引きされていく数値を覚えておいて、最後にまとめれば良いのではないかという気がして書いてみた
    • ひたすらWAで、駄目なケースをずっと考えていた
    • 終了10分前くらいにうまくいかなさそうなケースを思いついたけど、どう対処して良いかわからなかった
      • 打ち消しあって0にならないといけないのに、ゴールの状態に合わせるときに整数割り算で切り捨てが発生して0にならないような場合
    • 解説見たら全然アルゴリズム違った
    • 解法に確信がない問題に時間をかけては駄目だ
  • B
    • 読んだだけ
    • 普通にやったらN^2になってだめで、どうするんだろう、空間分割とかやるのかなあ
    • と思ったくらいで後回しにしていて考える時間がなかった
  • C
    • きっと約数関係でグラフにして二部マッチングだろうなあ、N=100というところからも
    • というくらいまでは考えたけど、どうすれば二部マッチングが適用できる形になるのかわからなかった
    • 蟻本が手元になかったのが痛い
  • F
    • 読んだだけ
  • H
    • 読んだだけ
    • 木にしてDPかなあ、くらい
    • 戦略としてはDじゃなくてこっちを考えておくべきだった
  • I
  • 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];
			}
		}
		ArrayList<Product> add = new ArrayList<Product>();
		ArrayList<Product> sub = new ArrayList<Product>();
		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<Product> {
		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<Cell> 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<Cell> 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<Cell> forward = new ArrayList<Cell>();
				ArrayList<Cell> backward = new ArrayList<Cell>();
				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() {
		PriorityQueue<State> q = new PriorityQueue<State>();
		int[] ord = new int[N];
		for (int i = 0; i < N; ++i) {
			ord[i] = i;
		}
		q.add(new State(0, ord));
		HashSet<State> visited = new HashSet<State>();
		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<State> {
		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);
		}

	}

}
 |