2011-03-25SRM300台を練習していく
SRM 301 IndicatorMotionReverse
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
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
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
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; } }
コメント