2441-Arrange the Bulls

問題（外部リンク）

2441 -- Arrange the Bulls

実装の概要

空いているところに牛を配置する問題。深さ優先探索では間に合いません。
ただ、nおよびmの最大値は大きくないのでビットDPであればで求めることができます。
具体的には、例えば1101(2進数)を1、3、4番目のスペースに既に牛が配置されているということにすれば更にそこに次の牛を配置できるかはAND演算で調べることができます。
簡単のため、牛は必ず入力された順に配置されると考えて大丈夫です。
入力例であれば、まず牛1は1および4に配置可能なのでdp[1][0]とdp[8][0]が1になります（それぞれ2^0および2^3）。
次に、牛2は1または3に配置できますが、2進数で考えたときに値の更新が必要なインデックスは5（1+2^2）、9（8+2^0）、12（8+2^2）です。場合によっては同じインデックスに複数回加算することもあります。加算する値は前の状態のものを使います。
気をつけることとして、今回の問題ではメモリの制約が若干厳しいので途中経過までメモすることができません。（更に厄介なことにローカル環境ではそれでも動いてしまいました）
そのため、そもそも次の状態を計算するには直前の状態さえ分かれば十分なので配列の使い回しを行います。この方法であればメモリの制約もクリアできます。

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();

		int pos[][] = new int[n][];
		for(int i = 0; i < n; i++){
			int tmp = sc.nextInt();
			pos[i] = new int[tmp];

			for(int j = 0; j < pos[i].length; j++){
				pos[i][j] = sc.nextInt() - 1;
			}
		}

		//2のべき乗の配列を予め作っておく
		int powers[] = new int[21];
		for(int i = 0; i <= 20; i++){
			powers[i] = (int)Math.pow(2, i);
		}
		//dp[i][]: 配置がiの状態となるパターン数
		//途中経過もすべて格納しようとするとMLEになるので
		//2列だけ用意して随時使い回す
		int dp[][] = new int[powers[m]][2];

		//一匹目で初期化
		for(int i = 0; i < pos[0].length ; i++){
			dp[powers[pos[0][i]]][0] = 1;
		}

		for(int i = 1; i < n; i++){
			for(int j = 0; j < dp.length; j++){
				//jとなるような配置が存在するなら
				//（もしこれが0であるならば続ける必要がないので無視）
				if(dp[j][0] != 0){
					for(int k = 0; k < pos[i].length ; k++){
						int tmpIndex = pos[i][k];
						//tmpIndexが既に配置されていないところなら
						if((int)(j & powers[tmpIndex]) == 0){
							dp[j + powers[tmpIndex]][1] += dp[j][0];
						}
					}
				}
			}

			//配列の内容の移し替えおよびクリア
			for(int j = 0; j < dp.length; j++){
				dp[j][0] = dp[j][1];
				dp[j][1] = 0;
			}
		}

		long result = 0;

		//結果は0列目の総和で求められる
		for(int i = 0; i < dp.length; i++){
			result += dp[i][0];
		}

		System.out.println(result);
	}

}