2015 TCO Round 1A Easy - Similars

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13714&rd=16432

ある数字xとyが与えられた時、0〜9のうち同じ数字が存在する数だけSimilarityの値が高くなる。
(例)x=1124、y=1122 1と2が双方に出るのでSimilarityは2

数字の範囲LとRが与えられた時、L~Rのうちの2つの数字のペアのうち、
最も高いSimilarityを求める。

解き方


数字が10^5のため、全探索すると10^10で間に合わない。
このような場合、探索する集合を変換できないか考える。

今回は1〜9の出現数が答えであるので、
「数字の集合」→「1〜9までの出現数の集合」に変換できる。

このとき、集合の総数は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;
}

};

Share this

Related Posts

Previous
Next Post »