Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-27SRM300台を練習していく part4

SRM 309 ScoreRecomposition

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

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

特にいい方法が思い浮かばなかったのでnext_permutationを使った。

質問の数は高々10だから、順列の数は10! = 3,628,800。いける!


public class ScoreRecomposition {
	public int minError(String questions, int score) {
		int len = questions.length();
		int min = 99999;
		int[] scores = new int[len];
		for (int i = 0 ; i < len ; i++) {
			scores[i] = i + 1;
		}
		do {
			int sc = 0;
			for (int i = 0 ; i < len ; i++) {
				if (questions.charAt(i) == 'C') {
					sc += scores[i];
				}
			}
			if (sc == score) {
				int err = 0;
				for (int i = 0 ; i < len ; i++) {
					err = Math.max(err, Math.abs(i+1 - scores[i]));
				}
				if (err < min) {
					min = err;
				}
			}
		} while (next_permutation(scores));

		if (min == 99999) return -1;
		return min;
	}

	public boolean next_permutation(int[] num) {
		int len = num.length;
		int x = len - 2;
		while (x >= 0 && num[x] >= num[x+1]) {
			x--;
		}
		if (x == -1) return false;

		int y = len - 1;
		while (y > x && num[y] <= num[x]) {
			y--;
		}
		int tmp = num[x];
		num[x] = num[y];
		num[y] = tmp;
		java.util.Arrays.sort(num, x+1, len);
		return true;
	}
}