SnackDown 2016 - Jealous Numbers - ツバサの備忘録

問題

与えられた集合から、任意の2つの元が互いに素になっているような部分集合をつくり、最大となる要素数を出力する、というものです。
これをT回繰り返します。

解法

まずはじめに、1はすべて部分集合にいれることができるので、1が入力された回数だけ別にもっておき、最後にたすことにします。この後は2以上の数について考えます。
任意の2つの要素について互いに素でなければならないので、2の倍数、3の倍数…は集合の中に1つずつしか存在してはいけません。いろいろ結局のところ、集合の全ての要素を素因数分解したときに、任意の素数はその集合の中で1回ずつしか使われてはいけません(4や8のように、1つの数字で複数回使われるものは全部で1回とします)。ということで、それぞれの素数について、すでに使われたかどうかをビットで管理したDPについて考えたいのですが、素数は100個を超えているため、それでは間に合いそうにありません。
そこで、素数を2種類に分類します。具体的には、31以下の素数と、37以上の素数です。
なぜこう分けるかというと、31以下の素数は、2乗しても1000以下になっているからです。
ある数xが37以上の素因数を持っていたとき、残りの素因数は31以下になっています。もちろん、ある数xが37以上の素因数を持っていないときも、素因数はすべて31以下です。
31までの素数は全部で11個しかないので、これならビットでうまく管理をすることができます。なので、入力された全ての数字について、

素因数の最大値
31以下の素因数をビットで表したもの

の2つを調べておきます。
さて、DPを考えていきます。
dp[i][S]とします。 iは現在見ている素因数の最大値、Sはすでに使った素数の集合(ビットで管理します)です。このときに入れることのできる要素数の最大値がここには格納されます。

今、入力された数字の中で、素因数の最大値がiとなっている数を1つもってきて、31以下の素因数のビットがBであるとしたとき、

SとBの論理和がSの場合
dp[i][S] = max(dp[i-1][S],1+dp[i-1][S-B])
1でない場合
dp[i][S] = max(dp[i-1][S])

となります。i-1は、実際にはi-1ではなく、iの1つ前の素数となります。
あとは、任意のiごとに入力された数を整理して、このDPの更新を繰り返していけば答えがもとまります。
途中で変なことをしたり、繰り返しの作業をかなり効率化しないと、時間オーバーになる可能性が高いです。 $2^{11}$ でいいところを $2^{12}$ で書いていてずっとTLEを連発していました(気づくのに数日かかりました)。

提出コードは以下になります。

#include <bits/stdc++.h>
#define N 10005
using namespace std;

bool primels[N + 5] = {0};
vector<int> primes;
int prime[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
pair<int, int> memo[1005];
map<int, vector<int>> a;
int dp[2][5000] = {0};
int n;
void sprime() {
  int i, j;
  primels[0] = 1;
  primels[1] = 1;
  for(i = 2; i <= N; ++i)
    if(!primels[i]) {
      primes.push_back(i);
      for(j = 2; i * j <= N; ++j) primels[i * j] = 1;
    }
}

int solve();

int main() {
  sprime();
  int t, i, x, one = 0, j, now, maxp = 0;
  for(i = 2; i <= 1000; ++i) {
    x = i;
    now = 0;
    maxp = 0;
    for(j = 0; j < 11; ++j)
      if(x >= prime[j] && x % prime[j] == 0) {
        while(x > 0 && x % prime[j] == 0) x /= prime[j];
        now += (1 << j);
        maxp = prime[j];
      }
    maxp = max(maxp, x);
    memo[i] = make_pair(maxp, now);
  }
  cin >> t;
  while(t) {
    one = 0;
    cin >> n;
    for(i = 0; i < n; ++i) {
      cin >> x;
      if(x == 1)
        ++one;
      else {
        now = memo[x].second;
        maxp = memo[x].first;
        a[maxp].push_back(now);
      }
    }
    cout << solve() + one << endl;
    for(j = 0; j < 2; ++j)
      for(i = 0; i < (1 << 11); ++i) dp[j][i] = 0;
    a.erase(a.begin(), a.end());
    --t;
  }
  return 0;
}

int solve() {
  int ans = 0, now, nprime, bit = 0;
  for(int i = 0; i < primes.size(); ++i) {
    if(a.find(primes[i]) != a.end()) {
      for(int j = 0; j < (1 << 11); ++j)
        dp[bit][j] = dp[1 - bit][j];
      for(int j = 0; j < a[primes[i]].size(); ++j) {
        nprime = a[primes[i]][j];
        now = (1 << min(11, i + 1)) - 1 - nprime;
        for(int mask = now; mask >= 0; --mask &= now) {
          dp[bit][mask + nprime] =
              max(dp[bit][mask + nprime],
                  dp[1 - bit][mask] + 1);
          ans = max(ans, dp[bit][mask + nprime]);
          if(mask == 0) break;
        }
      }
      bit = 1 - bit;
    }
  }
  return ans;
}