yukicoder : No.1598 4×4 Grid

昔のABCを思い出す。
https://yukicoder.me/problems/no/1598

問題

4*4のグリッドに1～16の値を1つずつ書き込む。
その時のスコアを、隣接セルの値の差の絶対値の総和とする。

グリッドの書き込み方16!通りにおいて、スコアがちょうどKとなるのは何通りか。

解法

隣接セル同士の値を加えたとき、大きい方の値はスコアに加算され、小さい方の値はスコアから減算される。
f(mask, v) := グリッドに小さい順に値を埋め、maskが示すセルに値を埋めたとき、そこまでの値の加減算の結果によるスコアがvとなる組み合わせの数

とし、次に小さい値を埋める位置を総当たりしよう。
隣接マスに自身より小さい値のマスがあればそれだけスコアに値が加算されるし、まだ埋まっていないマスがあればその分減算される。

int K;
ll dp[1<<16][1000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][500]=1;
	int mask;
	FOR(mask,1<<16) {
		k=__builtin_popcount(mask);
		FOR(j,1000) if(dp[mask][j]) {
			FOR(y,4) FOR(x,4) if((mask&(1<<(y*4+x)))==0) {
				int tar=j;
				if(y) {
					if((mask&(1<<((y-1)*4+x)))==0) tar-=k;
					else tar+=k;
				}
				if(y<3) {
					if((mask&(1<<((y+1)*4+x)))==0) tar-=k;
					else tar+=k;
				}
				if(x) {
					if((mask&(1<<(y*4+x-1)))==0) tar-=k;
					else tar+=k;
				}
				if(x<3) {
					if((mask&(1<<(y*4+x+1)))==0) tar-=k;
					else tar+=k;
				}
				dp[mask^(1<<(y*4+x))][tar]+=dp[mask][j];
			}
		}
	}
	
	cin>>K;
	cout<<dp[(1<<16)-1][500+K]<<endl;
	
}

まとめ

★4だけど実装は軽め。