Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-28SRM300台を練習していく part5

div1のeasyとmediumを中心に練習。

easyは200点以上が目標。

mediumは解けなくてもeditorial見ながら実装する。

SRM 303 Knights

|  SRM 303 Knights - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 303 Knights - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6070

蟻本を参考に最大流のオレオレライブラリを作って解いてみた。

でもまだ最小カットと最大流が等しくなることが直感的に理解できないんだよなぁ。


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Knights {
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}


	public int[] kx = {-2, -1, 1, 2, -2, -1, 1, 2};

	public int[] ky = {-1, -2, -2, -1, 1, 2, 2, 1};

	public int makeFriendly(int N, String[] pos) {
		int[][] field = new int[N][N];
		int knights = 0;
		for (String p : pos) {
			for (String kp : p.split(" ")) {
				int r = kp.charAt(0) - 'A';
				int c = Integer.valueOf(kp.substring(1)) - 1;
				knights++;
				field[r][c] = knights;
			}
		}


		init(knights + 2);
		Set<Integer> from = new HashSet<Integer>();
		Set<Integer> to = new HashSet<Integer>();
		for (int i = 0 ; i < N ; i++) {
			for (int j = 0 ; j < N ; j++) {
				if (field[i][j] > 0) {
					if ((i + j) % 2 == 1) {
						int s = field[i][j] - 1;
						from.add(s);
						for (int d = 0 ; d < 8 ; d++) {
							int dx = j + kx[d];
							int dy = i + ky[d];
							try {
								if (field[dy][dx] > 0) {
									int m = field[dy][dx] - 1;
									to.add(m);
									edge(s, m, 1);
								}
							} catch (Exception e) {
							}
						}
					}
				}
			}
		}

		int source = knights;
		int sink = knights + 1;
		for (int s : from) {
			edge(source, s, 1);
		}
		for (int m : to) {
			edge(m, sink, 1);
		}
		return max_flow(source, sink);
	}
}


SRM 300 JumpyNum

|  SRM 300 JumpyNum - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 300 JumpyNum - hama_DU@TopCoderへの道

まずn桁目の数字がdであるとき、d00...00 〜 d99...99 までのJumpyNumを数える変数dp[n][d]を用意しておく。この数はDPにより求められる。更新式は以下の通り。

for (int j = 0 ; j <= 9 ; j++) {
  if (Math.abs(j - d) >= 2) {
    dp[n][d] += dp[n-1][j]
  }
}

そして、num以下のJumpyNumの数を求める関数をcount(int num)とおくと、

求める答えは count(high) - count(low-1) となる。←ここまでは自力でやった

countを求めるアプローチは以下の通り。


まず、1〜9, 10〜99, 100〜999 , ... , 10...00〜99...99 のJumpyNumの数を、10^(numの桁数 - 1) - 1 まで求める。

次に、10^(numの桁数 - 1) から (numの先頭の桁の数) * 10^(numの桁数 - 1) - 1 までのJumpyNumの数を求める。

そして最後に、numの桁を最初から固定しながら、(numの先頭の桁の数) * 10^(numの桁数 - 1) から num までのJumpyNumの数を求める。

このとき、固定された桁同士がJumpyNumの条件を満たさなくなったら、その場でループを抜ける。

これら全ての和が求める数になる。

http://www.topcoder.com/stat?c=problem_statement&pm=4848


public class JumpyNum {
	long[][] dp = new long[15][10];

	public long count(int num) {
		if (num == 0) {
			return 0;
		}
		long count = 0;
		String snum = String.valueOf(num);
		int keta = snum.length();
		for (int i = 1 ; i <= keta - 1 ; i++) {
			for (int d = 1 ; d <= 9 ; d++) {
				count += dp[i][d];
			}
		}
		for (int d = 1 ; d <= (snum.charAt(0) - '0') - 1 ; d++) {
			count += dp[keta][d];
		}


		boolean isok = true;
		for (int l = keta - 1 ; l >= 1 ; l--) {
			int dig = snum.charAt(keta - l) - '0';
			int digp = snum.charAt(keta - l - 1) - '0';
			for (int d = 0 ; d < dig ; d++) {
				if (Math.abs(d - digp) >= 2) {
					count += dp[l][d];
				}
			}
			if (Math.abs(dig - digp) <= 1) {
				isok = false;
				break;
			}
		}
		if (isok) {
			count++;
		}
		return count;
	}

	public int howMany(int low, int high) {
		for (int i = 0 ; i <= 9 ; i++) {
			dp[1][i] = 1;
		}

		for (int d = 2 ; d <= 12 ; d++) {
			for (int i = 0 ; i <= 9 ; i++) {
				for (int j = 0 ; j <= 9 ; j++) {
					if (Math.abs(i - j) >= 2) {
						dp[d][i] += dp[d-1][j];
					}
				}
			}
		}
		long ans = count(high) - count(low-1);
		return (int) ans;
	}
}

SRM 313 PrefixFreeSets

|  SRM 313 PrefixFreeSets - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 313 PrefixFreeSets - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6569

辞書順にソートして条件に合うものを探す。


public class PrefixFreeSets {

	public int maxElements(String[] words) {
		java.util.Arrays.sort(words);

		int len = words.length;
		int cnt = 0;
		for (int i = 0 ; i < len ; i++) {
			int prex = 0;
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				if (words[j].startsWith(words[i])) {
					prex++;
				}
			}
			if (prex > 0) {
				words[i] = "Z";
				cnt++;
			}
		}
		return len - cnt;
	}
}



SRM 314 StandInLine

|  SRM 314 StandInLine - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 314 StandInLine - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6631

背の低い人から固定していく。


public class StandInLine {

	public int[] reconstruct(int[] left) {
		int[] tall = new int[left.length];
		for (int i = 0 ; i < left.length ; i++) {
			int cnt = 0;
			for (int pl = 0 ; pl < left.length ; pl++) {
				if (cnt == left[i] && tall[pl] == 0) {
					tall[pl] = i + 1;
					break;
				}
				if (tall[pl] == 0) {
					cnt++;
				}
			}
		}
		return tall;
	}
}