TopCoder SRM595: LittleElephantAndIntervalsDiv2
\( |L| = |R| \le 10 \)。よって高々 \( 2^{10} = 1024 \) 通りの塗り分け方を全て試せばよい。
想定解法的には LittleElephantAndIntervalsDiv1 のほうが簡単だと思う。
public class LittleElephantAndIntervalsDiv2 { public int getNumber(int M, int[] L, int[] R) { var colorings = new HashSet<string>(); for (int i = 0; i < (1 << L.Length); i++) { var array = new char[M]; for (int j = 0; j < L.Length; j++) { for (int k = L[j] - 1; k < R[j]; k++) { array[k] = (i & (1 << j)) != 0 ? '1' : '2'; } } colorings.Add(new string(array)); } return colorings.Count(); } }