Croc Champ 2013 - Round 1 : C. Beautiful IP Addresses

本番時間切れして、終了後に解いた問題。
Div2CやDiv1Aよりは若干難しいか？でもDiv1B位だけど。
http://codeforces.com/contest/292/problem/C

問題

いくつかの１桁の数値が与えられる。
それらの数字を最低１回以上使って、回文になるIPv4アドレスを答えよ。

解法

IPアドレスの数値部は最大12桁なので、回文になる以上最高でも6個までしか数字は使えない。
下1～6桁を全通り列挙し、それを反転して回文にした上、IPアドレスとして有効なピリオドの付け方を試せばよい。
ピリオドの付け方は、賢いやり方をしなくても各要素の文字列を1～3ケタになるように区切ったうえ、それぞれが0～255に収まるか試すだけ。

全列挙がO(N^N)だけどN<=6なので大した数にならない。
ピリオドの付け方もせいぜい27通りなので計算量は問題ない。

int N;
int C[10];
int N2[10];

int POW[10];
vector<string> R;

int num(char *str) {
	int l=strlen(str);
	int sep[4];
	int r=0,i,j;
	sep[0]=0;
	for(sep[1]=sep[0]+1;sep[1]<=sep[0]+3;sep[1]++) {
		if(sep[1]!=sep[0]+1 && str[sep[0]]=='0') continue;
		if(sep[1]==sep[0]+3 && (str[sep[0]]-'0')*100+(str[sep[0]+1]-'0')*10+(str[sep[0]+2]-'0')>255) continue;
		for(sep[2]=sep[1]+1;sep[2]<=sep[1]+3;sep[2]++) {
			if(sep[2]!=sep[1]+1 && str[sep[1]]=='0') continue;
			if(sep[2]==sep[1]+3 && (str[sep[1]]-'0')*100+(str[sep[1]+1]-'0')*10+(str[sep[1]+2]-'0')>255) continue;
			for(sep[3]=sep[2]+1;sep[3]<=sep[2]+3;sep[3]++) {
				if(l-sep[3]<1 || l-sep[3]>3) continue;
				if(sep[3]!=sep[2]+1 && str[sep[2]]=='0') continue;
				if(sep[3]==sep[2]+3 && (str[sep[2]]-'0')*100+(str[sep[2]+1]-'0')*10+(str[sep[2]+2]-'0')>255) continue;
				if(l!=sep[3]+1 && str[sep[3]]=='0') continue;
				if(l==sep[3]+3 && (str[sep[3]]-'0')*100+(str[sep[3]+1]-'0')*10+(str[sep[3]+2]-'0')>255) continue;
				
				char str2[20];
				j=0;
				FOR(i,l) {
					if(i==sep[1]||i==sep[2]||i==sep[3]) str2[j++]='.';
					str2[j++]=str[i];
				}
				str2[j]=0;
				R.push_back(str2);
			}
		}
	}
	return r;
}

int valid(char* str) {
	int ok=0;
	while(*str) ok |= N2[(*str++)-'0'];
	return (ok+1)==(1<<N);
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	if(N>=7) {
		_P("%d\n",0);
		return;
	}
	FOR(i,N){
		j=GETi();
		C[i]=j;
		N2[j]=1<<i;
	}

	POW[0]=1;
	FOR(i,9) POW[i+1]=POW[i]*N;
	
	
	char str[20],str2[20];
	for(j=N;j<=6;j++) {
		ZERO(str);
		ZERO(str2);
		FOR(i,POW[j]) {
			FOR(x,j) str[x]='0'+C[(i/POW[x])%N];
			if(!valid(str)) continue;
			FOR(x,j) str2[x]=str2[j*2-1-x]=str[x];
			num(str2);
			FOR(x,j) str2[x]=str2[j*2-2-x]=str[x];
			str2[j*2-1]=0;
			num(str2);
		}
	}
	
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%s\n",R[i].c_str());
	
	return;
}

まとめ

各要素が0～255に収まるか、非常に汚い方法で判定している。
sscanfとか使った方が楽かな？