2015 TCO Round 1A Easy - Similars
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13714&rd=16432
ある数字ｘとｙが与えられた時、０〜９のうち同じ数字が存在する数だけSimilarityの値が高くなる。
（例）ｘ＝１１２４、ｙ＝１１２２ １と２が双方に出るのでSimilarityは２
数字の範囲LとRが与えられた時、L~Rのうちの２つの数字のペアのうち、
最も高いSimilarityを求める。
解き方
数字が10^5のため、全探索すると10^10で間に合わない。
このような場合、探索する集合を変換できないか考える。
今回は１〜９の出現数が答えであるので、
「数字の集合」→「１〜９までの出現数の集合」に変換できる。
このとき、集合の総数は10^3（0から9の数字がそれぞれ出現するかどうか）となるので
全探索が可能になる。
コード
class Similars {
public: int maxsim(int L, int R) {
int dp[1024];
memset(dp,0,sizeof(dp));
for(int i=L;i<=R;i++){
int x=i;
int mask=0;
while(x>0){
mask|=1<<(x%10);
x/=10;
}
dp[mask]++;
}
int ret=0;
FORE(i,0,1024)FORE(j,0,1024){
if(i==j && dp[i]<=1)continue;
if(dp[i]==0 || dp[j]==0)continue;
ret=max(ret,__builtin_popcount(i&j));
}
return ret;
}
};
public: int maxsim(int L, int R) {
int dp[1024];
memset(dp,0,sizeof(dp));
for(int i=L;i<=R;i++){
int x=i;
int mask=0;
while(x>0){
mask|=1<<(x%10);
x/=10;
}
dp[mask]++;
}
int ret=0;
FORE(i,0,1024)FORE(j,0,1024){
if(i==j && dp[i]<=1)continue;
if(dp[i]==0 || dp[j]==0)continue;
ret=max(ret,__builtin_popcount(i&j));
}
return ret;
}
};
