TCO2012 1A

参加記録。惨敗

250 :
全部試す。
ソートを忘れて再提出。

500 :
AとBが等しくなる場合はたぶん無い。素数を分母か分子に振り分けるパターン数 / 2。
__builtin_popcountにlong long int を使ってシステムテストで落ちる。

1000 :
ざっと読んだだけ。

---

250

class EllysJuice {
public:
  vector <string> getWinners(vector <string> P)
  {
    vector<string> ret;
    vector<string> name = P;
    sort(name.begin(), name.end());
    name.erase(unique(name.begin(), name.end()), name.end());


    sort(P.begin(), P.end());

    do {
      double odd = 1;
      double even = 1;
      map<string, double> sum;

      for (int i = 0; i < P.size(); ++i) {
        if (i % 2 == 0) {
          sum[P[i]] += even / 2.0;
          even /= 2.0;
        } else {
          sum[P[i]] += odd / 2.0;
          odd /= 2.0;
        }       
      }

      double mx = 0;
      for (int i = 0; i < P.size(); ++i) {
        mx = max(mx, sum[P[i]]);
      }
     
      int cnt = 0;
      string s;
      for (int i = 0; i < name.size(); ++i) {
        if (sum[name[i]] == mx) {
          ++cnt;
          s = name[i];
        }
      }
     
      if (cnt == 1) ret.push_back(s);

    } while (next_permutation(P.begin(), P.end()));

    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());

    return ret;
  }
};

---

500

class EllysFractions {
public:
  long long getCount(int N)
  {
    const int M = 251;
    bool prime[M];
    fill(prime, prime + M, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i*i < M; ++i) {
      for (int j = 2; i*j < M; ++j) {
        prime[i * j] = false;
      }
    }

    lli p[M], size = 0;
    for (int i = 0; i < M; ++i) {
      if (prime[i]) p[size++] = i;
    }

    lli f[M];
    fill(f, f + M, 0);
    for (lli i = 2; i < M; ++i) {
      for (lli j = 0; j < size; ++j) {
        if (i % p[j] == 0) {
          f[i] |= 1LL << j;
        }
      }
    }

    for (int i = 1; i < M; ++i) {
      f[i] |= f[i - 1];
    }

    lli ret = 0;
    for (int i = 1; i <= N; ++i) {
      lli one = 0;
      for (int j = 0; j < 63; ++j) {
        if (f[i] & (1LL << (lli)j)) ++one;
      }
      ret += (1LL << one) / 2LL;
    }
    return ret;
  }
};