2011-08-15SRM300台を練習していく part9
SRM 322 ExtendedDominoes
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; } }
コメント