Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM 300 Dating

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

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

}