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; } };
0 件のコメント :
コメントを投稿