3046-Ant Counting

問題（外部リンク）

3046 -- Ant Counting

実装の概要

動的計画法を用います。
問題にあるように{1,2}と{2,1}などを重複して数えないように気をつける必要がありますが、そのためには「数字は必ず小さい順に並べる」と考えると分かりやすくなります。そしてdp[i][j]を「最後がi以下の数字である、要素数jの集合の個数」と定義します。あえて「i"以下"」とすることでループをシンプルに、かつ最後に答えを出す際の計算量を落とすことができます。
初期化の方法ですが、まず要素数が0の場合は1通り、要素数が1の場合は（より小さいiも含むため）i通りとなります。また、最後の数字が1である組み合わせは基本的に1通りです。
なお、iの値に応じて現実的に作れる文字列の長さの上限が決まるので、そこまでしかループを回す必要はありません。
これによって必要な値は全てi=Tの行に揃います。
具体的には、問題ページにある入力例の場合dpの中身は以下のようになります。

i＼j	0	1	2	3	4	5
0	0	0	0	0	0	0
1	1	1	1	0	0	0
2	1	2	3	2	0	0
3	1	3	5	5	3	1

例えばdp[2][3]=2となっていますが、これは「末尾が1以下でサイズが1の組み合わせに2を2つ追加するパターン」「末尾が1以下でサイズが2の組み合わせに2を1つ追加するパターン」「末尾が1以下でサイズが3の組み合わせ（注：該当無し）に何もしないパターン」の合計が「末尾が2以下でサイズが3の組み合わせ」となるためです。
なお、この方法でACになりましたがより工夫すればメモリの使用量を削減できる可能性があります。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] tmpArray = br.readLine().split(" ");

		int t = Integer.parseInt(tmpArray[0]);
		int a = Integer.parseInt(tmpArray[1]);
		int s = Integer.parseInt(tmpArray[2]);
		int b = Integer.parseInt(tmpArray[3]);

		int ants[] = new int[t + 1];
		//各ファミリーごとのアリの数を数える
		for(int i = 0; i < a ; i++){
			ants[Integer.parseInt(br.readLine())]++;
		}

		//i番目のグループまでの合計
		int total[] = new int[t + 1];

		for(int i = 1; i <= t; i++){
			total[i] = total[i-1] + ants[i];
		}

		//dp[i][j] : 最後にi以下を選んで作れる長さjのパターン数
		int[][] dp = new int[t+1][a+1];

		//初期化
		for(int i = 1; i <= t; i++){
			dp[i][1] = i;
			dp[i][0] = 1;
		}

		//1だけを選んで作れる組み合わせはどんな長さでも明らかに1通り
		for(int i = 1; i <= ants[1]; i++){
			dp[1][i] = 1;
		}
		for(int i = 2; i <= t; i++){
			for(int j = 2; j <= total[i] ; j++){
				for(int k = 0 ; k <= ants[i] && j - k >= 0 ; k++){
					dp[i][j] += dp[i - 1][j - k];
					dp[i][j] %= 1000000;
				}
			}
		}

		//debug
//		for(int i = 1; i <= t; i++){
//			for(int j = 1; j <= a; j++){
//				System.out.print(dp[i][j] + " ");
//			}
//			System.out.println();
//		}

		int result = 0;
		for(int i = s; i <= b; i++){
			result += dp[t][i];
			result %= 1000000;
		}
		System.out.println(result);
	}

}