TCO15 Round 1A easy: Similars

こっちのほうがmedより難しくないですか…

問題:TopCoder Statistics - Problem Statement

解法:LからRのすべての数について,0〜9のどの数が現れるかをbitmaskで管理する。(例えば21という数は「1」「2」「1と2」という数が出現するのでbitでは2,4,6になる)で,それぞれのbitmaskについて,カウントが2以上だったら条件をその数が出現するような数の組み合わせが存在するということなのでそれらのうち最大の数を求める。
以下ソースコード。今良く見たらこのコード10^5*10^3=10^8になってて良くないですね。ちゃんとやるんだったらそれぞれの数をbitmaskに変換するフェーズと,bitmaskの情報から一致している数字を探し出すフェーズの2つに分ければ計算量が10^6くらいになって良いと思います。

int cnt[1024];

void calc(int a) {
    int flag = 0;
    while (a) {
        int tmp = a%10;
        flag |= 1<<tmp;
        a /= 10;
    }
    for (int i = 0; i < 1024; i++) {
        bool ok = true;
        for (int j = 0; j < 10; j++) {
            if (((flag>>j)&1) == 0 && ((i>>j)&1) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) cnt[i]++;
    }
}

class Similars {
public:
    int maxsim(int L, int R) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = L; i <= R; i++) {
            calc(i);
        }
        int ret = 0;
        for (int i = 0; i < 1024; i++) {
            if (cnt[i] >= 2) {
                int tmp = __builtin_popcount(i);
                ret = max(ret, tmp);
            }
        }
        return ret;
    }
};