YUHA C88 謎解きコン : H - 恐怖！不幸を呼ぶ盾

これで実装難度★４ということは、実装自体はさほど要求しないコンテストだったということかな。
http://yuha-c88.contest.atcoder.jp/tasks/yuha_c88_h

問題

いわゆるスケルトンパズルである。
N個の単語群と空きマスが与えられるので、全単語を1回ずつ使って空きマスを埋めよ。

解法

Nの最大は10なので、N!通り単語の埋め方を総当たりすればよい。

int N;
string S[101];
int M;
string B[101];

vector<int> P;
int R[101][101];
int D[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	cin>>M;
	FOR(y,M) cin>>B[y];
	FOR(x,M) {
		for(y=M-1;y>=0;y--) if(B[y][x]!='#') {
			D[y][x]=1+D[y+1][x];
			if(D[y][x]>1 && (y==0 || B[y-1][x]=='#')) P.push_back(y*100+x);
		}
	}
	FOR(y,M) {
		for(x=M-1;x>=0;x--) if(B[y][x]!='#') {
			R[y][x]=1+R[y][x+1];
			if(R[y][x]>1 && (x==0 || B[y][x-1]=='#')) P.push_back(10000+y*100+x);
		}
	}
	sort(ALL(P));
	do {
		int ng=0;
		FOR(i,N) {
			int len;
			if(P[i]>=10000) len=R[(P[i]-10000)/100][P[i]%100];
			else len=D[P[i]/100][P[i]%100];
			if(len!=S[i].size()) ng++;
		}
		if(ng) continue;
		string B2[20];
		FOR(y,M) B2[y]=B[y];
		FOR(i,N) {
			r=P[i]/10000;
			y=(P[i]%10000)/100;
			x=P[i]%100;
			int len;
			if(r) len=R[y][x];
			else len=D[y][x];
			FOR(j,len) {
				if(B2[y][x]!='.' && B2[y][x]!=S[i][j]) ng++;
				B2[y][x]=S[i][j];
				if(r) x++;
				else y++;
			}
			if(ng) break;
		}
		if(ng==0) {
			cout<<M<<endl;
			FOR(y,M) cout<<B2[y]<<endl;
			break;
		}
		
		
	} while(next_permutation(ALL(P)));
}

まとめ

これにて大魔王撃破です。