kmjp's blog

競技プログラミング参加記です

yukicoder : No.2152 [Cherry Anniversary 2] 19 Petals of Cherry

入力から解法がだいぶ見えてしまうかも。
https://yukicoder.me/problems/no/2152

問題

1~19の順列Pを考える。
Pの各要素について、その位置に来てよい値の候補が与えられる。

全条件を満たすPのうち、転倒数が奇数・偶数のものをそれぞれ求めよ。

解法

BitDPで、使用済みの値と、ここまでの転倒数の偶奇をもってPの先頭から決めていく。

int L[19];
int M[19];

ll dp[1<<19][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,19) {
		cin>>L[i];
		FOR(j,L[i]) {
			cin>>x;
			M[i]|=1<<(x-1);
		}
	}
	
	dp[0][0]=1;
	int mask;
	FOR(mask,1<<19) FOR(y,2) {
		j=__builtin_popcount(mask);
		x=0;
		for(i=18;i>=0;i--) {
			if(mask&(1<<i)) {
				x^=1;
			}
			else if(M[j]&(1<<i)) {
				dp[mask^(1<<i)][y^x]+=dp[mask][y];
			}
		}
	}
	cout<<dp[(1<<19)-1][0]<<" "<<dp[(1<<19)-1][1]<<endl;
}

まとめ

★2.5でもいいかも。