北大日立マラソン第1回
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 - AtCoder
スタートダッシュ芸人してました
初日
焼きなましはすぐにわかったので軽く高速化・温度調整したやつを出した(CodinGameにも出たかったので巻いてた(結局出なかったが
初日にやったこと
- 初期解はランダム
- 近傍は正の辺の端点をもう一点に隣接させる(隣接先が空ならMove、他の点があるならSwap)(他の人と同じ)
- 近傍は一様ランダムセレクト
- 温度は5度から1.5度に線形に下げる(12ケースで調整)
- スコア変化量の計算は重みを32回足し引きすると思いますが、うち16回は事前に計算して持って遷移時に更新することで16回に減らせる
正の辺の端点をもう一点に隣接させる近傍なんですが、少なくとも一辺の得点がもらえるため、点のかたまりの遠くに飛ぶなどの明らかに無駄な近傍を除けて遷移効率が良くなります。こういう無駄な近傍を考えて除いたり、最適解ないし良い解を想像して、その形から離れるような近傍を除くというのは焼きなましではわりと頻出でとても効果が大きい。
その後
焼きなまし過程のVisualizerをつくった。赤がWeight=15、青がWeight=1、白線が近傍
↑最初から最後までのダイジェスト(飛び飛び)。
- 存外ふらふらするので初期解は中央にかためてランダム(壁にひっつくと遷移の自由度が下がって良くないので
- 良い解は円に近そうに見える(正方形や長方形よりも円のほうが辺数が多いことは確認した(yowaさんのtweetによると正八角形が最大らしい?
- 良い解は赤い(得点をもらえる辺はWeightが大きい辺に偏る)。ので近傍を一様ランダムセレクトではなく、
round(sqrt(Weight))
で重み付けランダムセレクトした
↑真ん中らへんの遷移を連続で
- 実際の遷移(白線)はかたまりの端と端が多い(かたまりの内側を動かすとスコアが大きく下がりやすく、焼きなましの遷移確率はスコアが大きく下がるときは低いのでそれはそう)。なのでこれをうまく使おうとしたけど難しかった。
その他
- GCCよりClangのほうが1.25倍速かった
- 他の人がやっているような高速化はだいたいやった
- 温度を再調整
↓初日submit
#include <algorithm> #include <cmath> #include <iostream> #include <vector> using namespace std; #define U(v) cerr << #v << ": " << (v) << endl constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; class timer { vector<timer> timers; int n = 0; public: double limit = 9.9; double t = 0; timer() {} timer(int size) : timers(size) {} bool elapses() const { return time() - t > limit; } void measure() { t = time() - t; ++n; } void measure(char id) { timers[id].measure(); } void print() { if (n % 2) measure(); for (int i = 0; i < 128; ++i) { if (timers[i].n) cerr << (char)i << ' ' << timers[i].t << 's' << endl; } cerr << " " << t << 's' << endl; } static double time() { #ifdef LOCAL return __rdtsc() / 3.3e9; #else unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2.8e9; #endif } } timer(128); #include <ctime> class { unsigned y = time(0); //unsigned y = 2463534242; public: unsigned next() { return y ^= (y ^= (y ^= y << 13) >> 17) << 5; } int next(int b) { return next() % b; } int next(int a, int b) { return next(b - a) + a; } double nextDouble(double b = 1) { return b * next() / 4294967296.0; } double nextDouble(double a, double b) { return nextDouble(b - a) + a; } int operator() (int b) { return next(b); } } rando; struct P { int x, y; P() {} P(int x, int y) : x(x), y(y) {} }; int V, E, S; vector<pair<int, int>> edges; char weight[501][501]; int vs[62][62]; char scores[501]; P ps[500]; P bestPs[500]; int eval() { int score = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) score += weight[e.first][e.second]; } return score; } void init() { vector<int> a; for (int i = 0; i < S * S; ++i) a.emplace_back(i); random_shuffle(a.begin(), a.end(), rando); for (int i = 0; i < V; ++i) { auto& p = ps[i]; p.x = a[i] % S + 1; p.y = a[i] / S + 1; vs[p.y][p.x] = i; } } void solve() { init(); copy_n(ps, V, bestPs); int score = eval(); int bestScore = score; for (int i = 0; i < V; ++i) { auto& p = ps[i]; for (int d = 0; d < 8; ++d) scores[i] += weight[i][vs[p.y + dy[d]][p.x + dx[d]]]; } double heat = 0; for (int iter = -1; ; ) { if ((++iter & 0xfff) == 0) { //double p = 1 - iter / 100000000.0; double p = 1 - (timer.time() - timer.t) / timer.limit; if (p < 0) { U(iter); break; } constexpr double InitialHeat = 5; constexpr double FinalHeat = 1.5; heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat); } int i, j, x, y; { unsigned r = rando.next(); auto& e = edges[(r >> 4) % edges.size()]; if (r & 8) { i = e.first; j = e.second; } else { j = e.first; i = e.second; } x = ps[j].x + dx[r & 7]; y = ps[j].y + dy[r & 7]; j = vs[y][x]; } if (i == j || x == 0 || x == S + 1 || y == 0 || y == S + 1) continue; auto& p = ps[i]; if (j == V) { int diff = - scores[i]; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; if (rando.nextDouble() < exp(diff * heat)) { score += diff; swap(vs[p.y][p.x], vs[y][x]); for (int d = 0; d < 8; ++d) { int v = vs[p.y + dy[d]][p.x + dx[d]]; scores[v] -= weight[i][v]; v = vs[y + dy[d]][x + dx[d]]; scores[v] += weight[i][v]; } scores[i] += diff; p = { x, y }; if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } } else { int diff = - scores[i] - scores[j]; if (max(abs(x - p.x), abs(y - p.y)) == 1) diff += weight[i][j]; vs[p.y][p.x] = vs[y][x] = V; for (int d = 0; d < 8; ++d) diff += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; vs[p.y][p.x] = j; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; vs[y][x] = i; if (rando.nextDouble() < exp(diff * heat)) { score += diff; for (int d = 0; d < 8; ++d) { int v = vs[p.y + dy[d]][p.x + dx[d]]; scores[v] -= weight[i][v] - weight[j][v]; v = vs[y + dy[d]][x + dx[d]]; scores[v] += weight[i][v] - weight[j][v]; } scores[i] = scores[j] = 0; for (int d = 0; d < 8; ++d) { scores[i] += weight[i][vs[y + dy[d]][x + dx[d]]]; scores[j] += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; } swap(p, ps[j]); if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } else { swap(vs[p.y][p.x], vs[y][x]); } } } copy_n(bestPs, V, ps); timer.print(); } int main() { timer.measure(); #ifdef LOCAL int type, seed; cin >> type >> seed; #endif cin >> V >> E; for (int i = 0; i < E; ++i) { int a, b, w; cin >> a >> b >> w; --a; --b; if (w != 0) { edges.emplace_back(a, b); weight[a][b] = weight[b][a] = w; } } cin >> S; S = (int)sqrt(S); { int E; cin >> E; for (int i = 0; i < E; ++i) { int a, b; cin >> a >> b; } } for (int i = 0; i < S + 2; ++i) fill_n(vs[i], S + 2, V); solve(); //cerr << "var d" << type * 6 + seed << " = [" << endl; //cerr << "[" << V << ',' << edges.size() << ',' << S << "]," << endl; //cerr << "["; //for (auto& e : edges) // cerr << e.first << ',' << e.second << ',' << (int)weight[e.first][e.second] << ','; //cerr << "]," << endl; //cerr << "["; //for (int i = 0; i < V; ++i) // cerr << i << ',' << ps[i].x << ',' << ps[i].y << ','; //cerr << "]," << endl; //cerr << "]" << endl; #ifdef LOCAL int score = 0; int esum = 0; int wsum = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) { score += weight[e.first][e.second]; ++esum; } wsum += weight[e.first][e.second]; } cerr << type * 6 + seed << "\t" << score << "\t" << wsum << "\t" << esum << "\t" << edges.size() << "\t" << V << "\t" << S << endl; #else for (int i = 0; i < V; ++i) { auto& p = ps[i]; cout << i + 1 << ' ' << (p.y - 1) * S + p.x << endl; } #endif return 0; }
↓最終submit
#include <algorithm> #include <cmath> #include <iostream> #include <vector> using namespace std; #define U(v) cerr << #v << ": " << (v) << endl constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; class timer { vector<timer> timers; int n = 0; public: double limit = 9.95; double t = 0; timer() {} timer(int size) : timers(size) {} bool elapses() const { return time() - t > limit; } void measure() { t = time() - t; ++n; } void measure(char id) { timers[id].measure(); } void print() { if (n % 2) measure(); for (int i = 0; i < 128; ++i) { if (timers[i].n) cerr << (char)i << ' ' << timers[i].t << 's' << endl; } cerr << " " << t << 's' << endl; } static double time() { #ifdef LOCAL return __rdtsc() / 3.3e9; #else unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2.8e9; #endif } } timer(128); #include <ctime> class { unsigned y = time(0); //unsigned y = 2463534242; public: unsigned next() { return y ^= (y ^= (y ^= y << 13) >> 17) << 5; } int next(int b) { return next() % b; } int next(int a, int b) { return next(b - a) + a; } double nextDouble(double b = 1) { return b * next() / 4294967296.0; } double nextDouble(double a, double b) { return nextDouble(b - a) + a; } int operator() (int b) { return next(b); } } rando; struct P { int x, y; char score; P() {} P(int x, int y) : x(x), y(y) {} }; int V, E, S; int neighborsSize; pair<pair<short, short>, pair<char, char>> neighbors[20000 * 64]; vector<pair<short, short>> edges; char weight[501][501]; short vs[62][62]; P ps[501]; P bestPs[501]; int eval() { int score = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) score += weight[e.first][e.second]; } return score; } void init() { vector<int> a(S * S); for (int i = 0; i < S * S; ++i) a[i] = i; sort(a.begin(), a.end(), [](int i, int j) { return max(abs(i % S - (S - 1) / 2.0), abs(i / S - (S - 1) / 2.0)) < max(abs(j % S - (S - 1) / 2.0), abs(j / S - (S - 1) / 2.0)); }); random_shuffle(a.begin(), a.begin() + V, rando); for (int i = 0; i < S + 2; ++i) fill_n(vs[i], S + 2, V); for (int i = 0; i < V; ++i) { auto& p = ps[i]; p = { a[i] % S + 1, a[i] / S + 1 }; vs[p.y][p.x] = i; } for (int i = 0; i < V; ++i) { auto& p = ps[i]; p.score = 0; for (int d = 0; d < 8; ++d) p.score += weight[i][vs[p.y + dy[d]][p.x + dx[d]]]; } } void solve() { init(); copy_n(ps, V, bestPs); int score = eval(); int bestScore = score; int ni = -1; const double InitialHeat = edges.size() / (double)V < 3 ? 2.5 : V <= 200 ? 3.5 : 5; const double FinalHeat = edges.size() / (double)V < 3 ? 0.5 : 2; double heat = 0; for (int iter = -1; ; ) { if ((++iter & 0xffff) == 0) { //double p = 1 - iter / 200000000.0; double p = 1 - (timer.time() - timer.t) / timer.limit; if (p < 0) { U(iter); break; } heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat); } short i, j; unsigned x, y; { if (++ni == neighborsSize) ni = 0; auto& n = neighbors[ni]; i = n.first.first; j = n.first.second; x = ps[j].x + n.second.first; y = ps[j].y + n.second.second; j = vs[y][x]; } if (i == j || max(x - 1, y - 1) >= (unsigned)S) continue; auto& p = ps[i]; if (j == V) { int diff = - ps[i].score; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; if (rando.nextDouble() < exp(diff * heat)) { score += diff; swap(vs[p.y][p.x], vs[y][x]); for (int d = 0; d < 8; ++d) { short v = vs[p.y + dy[d]][p.x + dx[d]]; ps[v].score -= weight[i][v]; v = vs[y + dy[d]][x + dx[d]]; ps[v].score += weight[i][v]; } p.score += diff; p.x = x; p.y = y; if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } } else { vs[p.y][p.x] = j; vs[y][x] = i; int diff = - ps[i].score - ps[j].score; for (int d = 0; d < 8; ++d) diff += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; for (int d = 0; d < 8; ++d) diff += weight[i][vs[y + dy[d]][x + dx[d]]]; if (rando.nextDouble() < exp(diff * heat)) { score += diff; for (int d = 0; d < 8; ++d) { short v = vs[p.y + dy[d]][p.x + dx[d]]; ps[v].score -= weight[i][v] - weight[j][v]; v = vs[y + dy[d]][x + dx[d]]; ps[v].score += weight[i][v] - weight[j][v]; } ps[i].score = ps[j].score = 0; for (int d = 0; d < 8; ++d) { ps[i].score += weight[i][vs[y + dy[d]][x + dx[d]]]; ps[j].score += weight[j][vs[p.y + dy[d]][p.x + dx[d]]]; } swap(p.x, ps[j].x); swap(p.y, ps[j].y); if (bestScore < score) { bestScore = score; copy_n(ps, V, bestPs); } } else { vs[p.y][p.x] = i; vs[y][x] = j; } } } copy_n(bestPs, V, ps); //timer.print(); } int main() { timer.measure(); #ifdef LOCAL int type, seed; cin >> type >> seed; #endif cin >> V >> E; for (int i = 0; i < E; ++i) { int a, b, w; cin >> a >> b >> w; --a; --b; if (w != 0) { edges.emplace_back(a, b); for (int i = 0; i < (int)round(sqrt(w)); ++i) { for (int d = 0; d < 8; ++d) { neighbors[neighborsSize++] = { { a, b }, { (char)dx[d], (char)dy[d] } }; neighbors[neighborsSize++] = { { b, a }, { (char)dx[d], (char)dy[d] } }; } } weight[a][b] = weight[b][a] = w; } } random_shuffle(neighbors, neighbors + neighborsSize, rando); cin >> S; S = (int)sqrt(S); { int E; cin >> E; for (int i = 0; i < E; ++i) { int a, b; cin >> a >> b; } } solve(); #ifdef LOCAL int score = 0; int esum = 0; int wsum = 0; for (auto& e : edges) { auto& a = ps[e.first]; auto& b = ps[e.second]; if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) { score += weight[e.first][e.second]; ++esum; } wsum += weight[e.first][e.second]; } cerr << type * 500 + seed << "\t" << score << "\t" << wsum << "\t" << esum << "\t" << edges.size() << "\t" << V << "\t" << S << endl; #else for (int i = 0; i < V; ++i) { auto& p = ps[i]; cout << i + 1 << ' ' << (p.y - 1) * S + p.x << endl; } #endif return 0; }