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