本番時間切れして、終了後に解いた問題。
Div2CやDiv1Aよりは若干難しいか?でもDiv1B位だけど。
http://codeforces.com/contest/292/problem/C
問題
いくつかの1桁の数値が与えられる。
それらの数字を最低1回以上使って、回文になる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とか使った方が楽かな?