class PairGame { public: set<pair<int, int> > decompose(int x, int y) { set<pair<int, int> > decomposed; while (x >= 1 && y >= 1) { decomposed.insert(MP(x, y)); if (x > y) { x -= y; } else { y -= x; } } return decomposed; } int maxSum(int a, int b, int c, int d) { set<pair<int, int> > A = decompose(a, b); set<pair<int, int> > B = decompose(c, d); int bestAnswer = -1; for (const auto& p : A) { if (B.count(p)) { MAX_UPDATE(bestAnswer, p.first + p.second); } } return bestAnswer; } }
oxx 229位 1864->1889 少しだけレーティングが上がりました。右肩下がりは止まったのでしょうか・・・。
class CandidatesSelection { public: vector <string> score; vector<int> result; set<ll> memo; ll hash(const vector<vector<int> >& v) const { ll hash = -1; for (const auto& x : v) { for (int w : x) { hash *= 31; hash += w; } hash *= 31; } return hash; } bool dfs(const vector<vector<int> >& v) { ll h = hash(v); if (memo.count(h)) { return false; } memo.insert(h); if (clock() / double(CLOCKS_PER_SEC) > 1.8) { return false; } bool ok = true; for (const auto& part : v) { if (!is_sorted(ALL(part))) { ok = false; break; } } if (ok) { return true; } for (const auto& magnitudeRelation : score) { bool ok = true; vector<vector<int> > next; for (const auto& part : v) { for (int i = 0; i + 1 < part.size(); ++i) { if (magnitudeRelation[part[i]] > magnitudeRelation[part[i + 1]]) { ok = false; break; } } if (!ok) { break; } map<char, vector<int> > m; for (int x : part) { m[magnitudeRelation[x]].push_back(x); } for (const auto& bucket : m) { next.push_back(bucket.second); } } if (!ok) { continue; } if (dfs(next)) { return true; } } return false; } string possible(vector <string> score, vector <int> result) { this->score.clear(); this->score.resize(score[0].size()); for (const string& s : score) { REP(i, s.size()) { this->score[i] += s[i]; } } this->result = result; memo.clear(); vector<vector<int> > initial; initial.push_back(result); string res = dfs(initial) ? "Possible" : "Impossible"; return res; } }
int main() { std::ios::sync_with_stdio(false); int S, T; cin >> S >> T; cout << T - S + 1 << endl; }
int main() { std::ios::sync_with_stdio(false); int N; cin >> N; map<string, int> votes; REP(n, N) { string name; cin >> name; votes[name]++; } int bestVotes = 0; string bestName; for (const auto& v : votes) { if (bestVotes < v.second) { bestVotes = v.second; bestName = v.first; } } cout << bestName << endl; }
double C[128][128]; double BIKKURI[128]; int main() { std::ios::sync_with_stdio(false); REP(i, 128) { C[i][0] = 1.0; } for (int i = 1; i < 128; ++i) { for (int j = 1; j < 128; ++j) { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } BIKKURI[0] = 1.0; for (int i = 1; i < 128; ++i) { BIKKURI[i] = BIKKURI[i - 1] * i; } int N; cin >> N; vector<int> coins; REP(n, N) { int coin; cin >> coin; coins.push_back(coin); } double sum = 0.0; REP(base, N) { int counter = 0; REP(other, N) { if (base == other) { continue; } if (coins[base] % coins[other] == 0) { ++counter; } } for (int left = 0; left <= N - 1; ++left) { int right = N - 1 - left; for (int leftHit = 0; leftHit <= counter && leftHit <= left; ++leftHit) { if (leftHit % 2 != 0) { continue; } int rightHit = counter - leftHit; if (rightHit > right) { continue; } sum += C[left][leftHit] * C[right][rightHit] * BIKKURI[counter] * BIKKURI[N - counter - 1]; } } } printf("%.20f\n", sum / BIKKURI[N]); }
const int DX[] = { 0, 0, 1, -1 }; const int DY[] = { 1, -1, 0, 0 }; vector<pair<int, int> > initialMachines; int N; vector<int> space(const vector<int>& xs, int X) { vector<int> ret; ret.push_back(xs[0] - 1); ret.push_back(1); REP(i, xs.size() - 1) { ret.push_back(xs[i + 1] - xs[i] - 1); ret.push_back(1); } ret.push_back(X - xs.back()); return ret; } int spacesX[64]; int spacesY[64]; ll calculate(const vector<pair<int, int> >& machines, int W, int H) { bool memo[64][64]; CLEAR(memo); int counter = 0; for (const auto& machine : machines) { counter += spacesX[machine.first] * spacesY[machine.second]; memo[machine.first][machine.second] = true; REP(dir, 4) { int x = machine.first + DX[dir]; int y = machine.second + DY[dir]; while (0 <= x && x < N * 2 + 1 && 0 <= y && y < N * 2 + 1 && !memo[x][y]) { counter += spacesX[x] * spacesY[y]; memo[x][y] = true; x += DX[dir]; y += DY[dir]; } } } return counter; } #ifdef _MSC_VER #include <Windows.h> ll getTime() { return GetTickCount(); } #else #include <sys/time.h> ll getTime() { struct timeval tv; gettimeofday(&tv, NULL); ll result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL; //cerr << result << endl; return result; } #endif // http://www.jstatsoft.org/v08/i14/xorshift.pdf unsigned int xor128() { // 周期は 2^128-1 static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t; t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } //TODO:状態を表す型/構造体を作成する class STATE { public: //TODO:コンストラクタに必要な引数を追加する explicit STATE(); void next(); void prev(); double energy(); public: vector<pair<int, int> > machines; int src, dst; }; class SimulatedAnnealing { public: //TODO:コンストラクタに必要な引数を追加する SimulatedAnnealing(); STATE run(); private: static const int TIME_LIMIT; double calculateProbability(double score, double scoreNeighbor, double temperature); }; //TODO:コンストラクタに必要な引数を追加する SimulatedAnnealing::SimulatedAnnealing() { } //TODO:計算時間をミリ秒単位で設定する const int SimulatedAnnealing::TIME_LIMIT = 3900; STATE SimulatedAnnealing::run() { const ll timeStart = getTime(); const ll timeEnd = timeStart + TIME_LIMIT; STATE state; double energy = state.energy(); STATE result = state; double minEnergy = energy; int counter = 0; ll timeCurrent; while ((timeCurrent = getTime()) < timeEnd){ REP(loop, 100) { state.next(); const double energyNeighbor = state.energy(); const double random = xor128() * 0.00000000023283064365386962890625; const double probability = calculateProbability(energy, energyNeighbor, (double)(timeEnd - timeCurrent) / (double)(timeEnd - timeStart) + 1e-8); if (random < probability){ //Accept if (minEnergy > energyNeighbor) { #ifdef _MSC_VER fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor); #endif minEnergy = energyNeighbor; result = state; } //fprintf(stderr, "Accepted %.5lf -> %.5lf : minEnergy=%.5lf\n", energy, energyNeighbor, minEnergy); energy = energyNeighbor; } else { //Decline state.prev(); //fprintf(stderr, "Declined\n"); } ++counter; } } fprintf(stderr, "counter:%d minEnergy:%.5lf\n", counter, minEnergy); return result; } double SimulatedAnnealing::calculateProbability(double energy, double energyNeighbor, double temperature) { if (energyNeighbor < energy) { return 1; } else { const double result = exp((energy - energyNeighbor) / (temperature + 1e-9) * 0.040); //fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result); return result; } } //TODO:初期状態を作る関数を記述する STATE::STATE() { machines = initialMachines; } //TODO:遷移後の状態を作る関数を記述する void STATE::next() { if (machines.size() == 1) { return; } src = xor128() % machines.size(); do { dst = xor128() % machines.size(); } while (src == dst); swap(machines[src], machines[dst]); } //TODO:遷移前の状態を作る関数を記述する // 高々一つ前の状態までに戻れれば良い void STATE::prev() { if (machines.size() == 1) { return; } swap(machines[src], machines[dst]); } //TODO:状態のエネルギーを計算する関数を記述する // 状態はエネルギーの低い所に遷移する点に注意する double STATE::energy() { return -calculate(machines, N * 2 + 1, N * 2 + 1); } int main() { std::ios::sync_with_stdio(false); ifstream cin("C:\\cygwin\\home\\nodchip\\procon\\abc008_4.2.in.txt"); int W, H; cin >> W >> H; cin >> N; vector<pair<int, int> > machines; vector<int> xs; vector<int> ys; REP(n, N) { int x, y; cin >> x >> y; machines.push_back(MP(x, y)); xs.push_back(x); ys.push_back(y); } sort(ALL(xs)); sort(ALL(ys)); vector<int> spacesX = space(xs, W); vector<int> spacesY = space(ys, H); REP(i, spacesX.size()) { ::spacesX[i] = spacesX[i]; } REP(i, spacesY.size()) { ::spacesY[i] = spacesY[i]; } for (auto& machine : machines) { machine.first = distance(xs.begin(), find(ALL(xs), machine.first)) * 2 + 1; machine.second = distance(ys.begin(), find(ALL(ys), machine.second)) * 2 + 1; } initialMachines = machines; STATE state = SimulatedAnnealing().run(); cout << calculate(state.machines, N * 2 + 1, N * 2 + 1) << endl; //ll bestCounter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1); //bool updated = true; //while (updated) { // updated = false; // for (int n = 0; n + 1 < N; ++n) { // swap(machines[n], machines[n + 1]); // ll counter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1); // if (bestCounter < counter) { // bestCounter = counter; // updated = true; // } // else { // swap(machines[n], machines[n + 1]); // } // } //} //cout << bestCounter << endl; }
順位 | ユーザ名 | アルバム | 投票 | コイン | 金塊ゲーム | 得点 / Total | |
19 | nodchip | 100 00:36 | 100 02:24 | 100 (1) 104:39 | 99 (15) 87:48 | 399 (16) | 184:39 |
どうにかこうにか1ページ目に入ることができました。Dは動的計画法だそうです。動的計画法は苦手です。