hama_DU@TopCoderへの道

SRM 322 ExtendedDominoes

Java, div1q2 |

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

閉路を全部検出して、閉路のつながり方を全部調べようとして分けわかんなくなった。

editorialを見て解法を理解。自力では解けなかった。

public class ExtendedDominoes {
	public long countCycles(String[] pieces) {
		boolean[][] edges = new boolean[10][10];
		for (String line : pieces) {
			int a = line.charAt(0) - '0';
			int b = line.charAt(1) - '0';
			edges[a][b] = true;
			edges[b][a] = true;
		}
		
		long answer = 1L;
		for (int a = 0 ; a <= 9 ; a++) {
			int cnt = 0;
			for (int b = 0 ; b <= 9 ; b++) {
				if (edges[a][b]) {
					cnt++;
				}
			}
			if (cnt % 2 == 1) {
				return 0;
			}
			long rec = 1L;
			for (int i = 1 ; i <= cnt ; i += 2) {
				rec = rec * i;
			}
			answer *= rec;
		}
		return answer;
	}
}