hama_DU@TopCoderへの道

SRM 301 IndicatorMotionReverse

Java, div1q1, div2q2 |

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

状態の差分をとって、差分が連続しているものをグループ化する。

方針は割とすぐ浮かんだ。

それにしてもなんだかアホなコード。130点ぐらい

public class IndicatorMotionReverse {

	public int diff(char a, char b) {
		if (a == b) {
			return 0;
		}
		if (a == '-') {
			if (b == 'N') {
				return 45;
			}
			if (b == '|') {
				return 90;
			}
			if (b == '/') {
				return -45;
			}
		}
		if (a == 'N') {
			if (b == '|') {
				return 45;
			}
			if (b == '/') {
				return 90;
			}
			if (b == '-') {
				return -45;
			}
		}
		if (a == 'N') {
			if (b == '|') {
				return 45;
			}
			if (b == '/') {
				return 90;
			}
			if (b == '-') {
				return -45;
			}
		}
		if (a == '|') {
			if (b == '/') {
				return 45;
			}
			if (b == '-') {
				return 90;
			}
			if (b == 'N') {
				return -45;
			}
		}
		if (a == '/') {
			if (b == '-') {
				return 45;
			}
			if (b == 'N') {
				return 90;
			}
			if (b == '|') {
				return -45;
			}
		}
		return -1;
	}

	public String diffToProgram(int diff, int ct) {
		String p = "";
		String command = "";
		int last = ct % 99;
		int len = ct / 99;

		if (diff == 0) {
			command += "S";
		}
		if (diff == 45) {
			command += "R";
		}
		if (diff == -45) {
			command += "L";
		}
		if (diff == 90) {
			command += "F";
		}
		for (int i = 0 ; i < len ; i++) {
			p += command + "99";
		}

		if (last >= 1) {
			if (last <= 9) {
				p = command + "0" + last + p;
			} else {
				p = command + last + p;
			}
		}

		return p;
	}

	public String getMinProgram(String[] actions) {
		String to = "";
		String program = "";
		for (String action : actions) {
			to += action;
		}
		if (to.length() == 1) {
			return "";
		}


		int[] diffs = new int[to.length()-1];
		for (int i = 1 ; i < to.length() ; i++) {
			diffs[i-1] = diff(to.charAt(i-1), to.charAt(i));
		}

		int diff = diffs[0];
		int ct = 1;
		for (int i = 1 ; i < to.length() - 1 ; i++) {
			if (diff == diffs[i]) {
				ct++;
			} else {
				program += diffToProgram(diff, ct);
				diff = diffs[i];
				ct = 1;
			}
		}
		program += diffToProgram(diff, ct);

		if (program.length() > 100) {
			return program.substring(0, 97) + "...";
		}
		return program;
	}
}

SRM 300 Dating

Java, div1q1, div2q2 |

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

やるだけ。170点ぐらい

public class Dating {

	public String dates(String circle, int k) {
		int[][] persons = new int[circle.length()][3];
		int men = 0;
		int women = 0;
		for (int i = 0 ; i < circle.length() ; i++) {
			char ch = circle.charAt(i);
			if ('A' <= ch && ch <= 'Z') {
				persons[i][0] = 0;
				persons[i][1] = ch - 'A';
				men++;
			} else {
				persons[i][0] = 1;
				persons[i][1] = ch - 'a';
				women++;
			}
			persons[i][2] = i+1;
		}
		persons[circle.length() - 1][2] = 0;

		String result = "";
		int idx = 0;
		int ct = 1;
		dqn: while (true) {
			int fs = idx;
			int fct = ct;
			while (ct < k) {
				idx = persons[idx][2];
				if (persons[idx][1] < 999) {
					ct++;
				}
				if (fs == idx && fct == ct) {
					break dqn;
				}
			}
			if (ct == k) {
				ct = 0;
				int oidx = idx;
				int best = 999;
				int best_oidx = -1;
				do {
					oidx = persons[oidx][2];
					if (persons[idx][0] != persons[oidx][0]) {
						if (persons[oidx][1] < best) {
							best = persons[oidx][1];
							best_oidx = oidx;
						}
					}
				} while (oidx != idx);
				if (best == 999) {
					System.out.println("out " + result);
					break;
				}
				result +=
					String.valueOf(circle.charAt(idx)) +
					String.valueOf(circle.charAt(best_oidx)) +
					" ";

				persons[idx][1] = 999;
				persons[best_oidx][1] = 999;
			}
		}

		if (result.length() == 0) {
			return result;
		}
		return result.substring(0, result.length() - 1);
	}

}

SRM 302 DivisorInc

Java, div1q1, div2q3 |

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

はじめはNを増やすように探索しようかと考えたが、間に合わないので方針を転換。

Mを減らしながら、メモ化再帰ならいける。

こういう問題を素早く解くのは苦手だ・・・110点ぐらい。

import java.util.ArrayList;
import java.util.List;

public class DivisorInc {

	public int inf = 99999999;

	public List<Integer> sel(int x) {
		List<Integer> l = new ArrayList<Integer>();
		int sq = (int)Math.sqrt(x);
		for (int i = 2 ; i <= sq ; i++) {
			if (x % i == 0) {
				l.add(i);
				if (i != 2) {
					l.add(x / i);
				}
			}
		}

		return l;
	}

	public int memo[] = new int[100001];

	public int rsearch(int N, int M) {
		if (memo[M] != 0) {
			return memo[M];
		}

		if (N == M) {
			return 0;
		}
		if (N > M) {
			return inf;
		}

		List<Integer> s = sel(M);
		java.util.Collections.sort(s);
		int lne = s.size();

		int min = inf;
		for (int i = lne - 1 ; i >= 0 ; i--) {
			min = Math.min(min, rsearch(N, M - s.get(i)) + 1);
		}
		memo[M] = min;
		return min;
	}

	public int countOperations(int N, int M) {
		if (N == M) {
			return 0;
		}
		if (sel(N).size() * sel(M).size() == 0) {
			return -1;
		}
		int ret = rsearch(N, M);
		if (ret >= inf) {
			return -1;
		}
		return ret;
	}
}

SRM 301 EscapingJail

Java, div1q2 |

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

ワーシャルフロイド法というものを学んだ。

public class EscapingJail {

	public int getMaxDistance(String[] chain) {
		int inf = 100000000;
		int len = chain.length;
		int[][] dist = new int[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				char ch = chain[i].charAt(j);
				if (ch ==' ') {
					dist[i][j] = inf;
				} else if ('A' <= ch && ch <= 'Z') {
					dist[i][j] = 36 + ch - 'A';
				} else if ('a' <= ch && ch <= 'z') {
					dist[i][j] = 10 + ch - 'a';
				} else {
					dist[i][j] = ch - '0';
				}
			}
		}


		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				for (int k = 0 ; k < len ; k++) {
					dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
				}
			}
		}

		int max = 0;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				max = Math.max(max, dist[i][j]);
			}
		}
		if (max == inf) {
			return -1;
		}
		return max;
	}
}