Hatena::Grouptopcoder

blu_rayの日記

2011-09-10

SRM 517 Div2

| 03:39

ox-

250. MonochromaticBoard / Passed System Test

無駄に時間かかった。

500. CompositeSmash / Failed System Test

Nをとりあえず素因数分解して、vectorに放り込んで、

vectorの長さがおそらく最大でも16前後だろうということでbitで状態生成して全探索。

とかしてるけど、そんな必要なかった。

このコードだとNとtargetが互いに素の場合(="NO")で死ぬのに気づけなかった。悔しい。

const int MAX_N = 100012;
bool sieve[MAX_N];
vector<int> prime, list;

class CompositeSmash {
public:
  bool isInvalid(int S, int size) {
    if (S == 0) return true;
    int i;
    rep(i,size) if (!((1<<i)&S)) return false;
    return true;
  }
  string thePossible(int N, int target) {
    if (N == target) return "Yes";
    if (N < target) return "No";
    int i, j;
    fill(sieve, sieve+MAX_N, true);
    sieve[0] = sieve[1] = false;
    for(i=2;i<MAX_N;i++) if (sieve[i]) {
      prime.push_back(i);
      for(j=i+i;j<MAX_N;j+=i) sieve[j] = false;
    }
    
    int temp = N;
    int sz = prime.size();
    rep(i,sz) {
      while (temp % prime[i] == 0) {
        temp /= prime[i];
        list.push_back(prime[i]);
      }
    }
        
    int lsz = list.size();
    if (lsz == 1) return "No"; // これがなくて脂肪
    for(int S=1;S<(1<<lsz);S++) {
      if (isInvalid(S, lsz)) continue;
      int rhs = 1, lhs = 1;
      rep(i,lsz) {
        if ((1<<i)&S) {
          rhs *= list[i];
        } else {
          lhs *= list[i];
        }
      }
      if (rhs % target != 0 && lhs % target != 0) return "No";      
    }
    return "Yes";
  }
};

isInvalid()は意味ないとおもう

1000. CompositeSmash / Unopened

rate := 967 -> 954