SRM 653 Div. 1 Easy: CountryGroupHard
問題
TopCoder Statistics - Problem Statement
色んな国から来たN人が1列に座っていて、同じ国から来た人は隣り合って固まって座っている。何人かに、同じ国から来た人数を聞いた。その情報だけで、まだ聞いてない人がどう答えるか当てることが出来るか。
解法
DFSで解こうとゴニョゴニョ頑張って通した。1304->1445
コード
import java.util.Arrays; public class SRM653Div1E { public String solve(int[] a) { if (DFS(a, 0) == 1) { return "Sufficient"; } else { return "Insufficient"; } } static int DFS(int[] row, int posi) { // 普通のokなら1を、2パターン以上出ているなら2を、行き止まりなら0を返す if (posi == row.length) { String check = Arrays.toString(row); if (check.indexOf("0, 0") != -1) { return 2; } else { return 1; } } int choice = 0; while (posi < row.length) { choice = row[posi]; if (choice > 0) { break; } else { posi++; } } if (posi == row.length) { String check = Arrays.toString(row); if (check.indexOf("0, 0") != -1) { return 2; } else { return 1; } } int pattern = 0; for (int start = posi + 1 - choice; start <= posi; start++) { int[] newrow = new int[row.length]; for (int j = 0; j < newrow.length; j++) { newrow[j] = row[j]; } if (start < 0 || start + choice - 1 >= newrow.length) { continue; } boolean newrowmade = true; for (int p = start; p < start + choice; p++) { if (newrow[p] != 0 && newrow[p] != choice) { newrowmade = false; break; } newrow[p] = -1; } if (!newrowmade) { continue; } pattern += DFS(newrow, start + choice); // System.out.println(Arrays.toString(newrow)); if (pattern >= 2) { return 2; } } return pattern; } }