2015 TCO 1A Similars

2015/04/13 (Mon) srm 全探索

問題

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

区間 $[L,R]$ から相異なる整数のペアを選び、十進数表記したときに共通して含まれている数字の種類数の最大値は？

方針

区間内の全ての整数について、含まれる数字からなる集合を求め、その集合をキーとする配列の要素を 1 加算します。 最終的な値が 1 以上の異なる集合の対について全探索し、それらの交わりの要素数の最大値を求めます。 値が 2 以上の 1 つの集合も含めます。

実装

class Similars {
public:
    int maxsim( int L, int R ) {
        vector<int> v(1<<10);
        for(int i=L;i<=R;i++){
            stringstream ss;
            ss << i;
            string s;
            ss >> s;
            int bs = 0;
            for(char c : s) bs |= 1<<(c-'0');
            v[bs]++;
        }
        int ans = 0;
        rep(i,1<<10)rep(j,i){
            if(v[i]>=2) ans = max(ans,popcount(i));
        }
        rep(i,1<<10)if(v[i]>=1){
            rep(j,i)if(v[j]>=1){
                ans = max(ans, popcount(i&j));
            }
        }
        return ans;
    }

    int popcount(int x){
        int res = 0;
        while(x){
            res += x&1;
            x>>=1;
        }
        return res;
    }
};