Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-25SRM300台を練習していく

SRM 301 IndicatorMotionReverse

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

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;
	}
}