Yandex Algorithm 2018 Optimization track. Round 2 News freshness
暫定3位でした。険しい。問題自体はとてもおもしろかった。
greedy
巡回するサイトを1つずつ順番に決めていってパスをgreedyにつくります。パスがつくり途中だと2週目以降にいつどのサイトを訪れるかが定まらずスコアに加味できないので困ります。そこでパスの周期（timeToIndexの和）を決め打ちします。あらかじめ決めた周期（それ以外認めない）になるようにパスをつくることで、つくり途中でも2週目以降のスコアを計算できるようになります。
実装としては、最初は自由にパスを伸ばします。そして周期-150を切ったら、パスの後尾からランダムに伸ばして周期ジャストでパスの先頭に戻れるものの中からgreedyに1つ選ぶなどすると、だいたい成功します。
評価関数は、testerスコアの期待値 / すべてのパスのtimeToIndexの和としました。すべてのパスのtimeToIndexの和でわることで、timeToIndexあたりのスコアが高い効率のよいサイトが選ばれていきます。
あとはテキトーな周期で何回かgreedyしてmaxをとれば8600点以上が出ました。
周期
周期についていろいろ。
timeToIndexあたりのスコアがよいサイトばかりを選ぶとtimeToIndexが小さいので周期が短くなります。しかし周期が長いと週回数が少なくなり、1つのクローリングが影響する箇所が少なくなるのでよいスコアを得やすいです。短いことにも長いことにもメリットがあるので周期には短すぎず長すぎないベターな長さが存在します（実験によって確認）。
ベターな周期はすべてのサイトのtimeToIndexの和の45%-70%(5000-20000)ぐらいになるようです。またパス長は周期を長くするためにNギリギリであることが理想的ですがgreedyによって得られるパス長はNの65%-100%くらいになります。
ほどよい周期のパスをgreedyで得るために評価関数をtesterスコアの期待値 / pow(すべてのパスのtimeToIndexの和, timeCoef)に変えます。timeCoefが1に近いほど周期が短く、0に近いほど長くなります。timeCoefのよさげな値は3分探索で求めることができますがgreedy1回がとても重いのでやめました。timeCoefのよさげな値をローカルで時間をかけて求めて、testcaseパラメータと最小二乗法でえいっしたらこんな式に、
timeCoef = sqrt(S / (double)numberOfEdges) * -7.836528104606689 + 0.7974926014955707;
timeCoefは決まりましたが、そのtimeCoefに対応する周期は事前にわかりません。周期が長すぎるとパス長制限で構築に失敗しますし、短いほどスコアが悪くなります。なので2分探索で構築に失敗しない最大の周期を求めます。
ここまででよさげな周期を求めることができました。これで8700点ぐらい
周期には他にも着眼点があって、周期がtopicのfreqの倍数のときスコアがよくなります。というのも、そうであるときニュースの生成周期とクローリングの周期がそろうので、1週目で高スコアをとれれば、すべての周回で高スコア（同スコア）をとれるためです 。周期がずれてるとすべての周回で高スコアをとるのは難しくなります。
なのでいずれかのtopicのfreqの倍数であるような周期の中から2分探索すると8740点ぐらい
山登り
この問題はぱっと見山登り/焼きなましできない系に見えますができます。
timeToIndexの和が110程度の部分パスをランダムに選びます。そしてtimeToIndexの和が同じであるようにランダムに生成した部分パスと置換します。こういう近傍だと変更域以外の時間がずれないので山登り/焼きなましが有効ななだらかに近い探索空間になります。
greedyの結果を山登りして8790点ぐらい
入力バイナリから画像を作成するプログラムを公開しました
圧縮する入力バイナリは２次元のradianceのデータなようです。 このデータの画像はnetCDFデータのビューアから見ることができるようで、見るためにはnetCDFデータをビューアで開く、Rad行をダブルクリック、Create a 2D plotを選択します。
とりあえず入力バイナリがどんなものか理解するために、入力バイナリから同じ画像を作成するプログラムを書きました。動作にはPython3、ライブラリPillowが必要です。（ソースコードはブログ最下部）
py script.py bin_4obs/OR_ABI-L1b-RadC-M3C01_G16_s20172101802185_e20172101804558_c20172101805000.bin
これで画像が作成されます。色がぜんぜん違いますが、グラデーション色が違うだけでradianceはビューアと一致しています。
入力バイナリは、２次元を１次元につぶした２バイトのunsigned short？のradianceの基本値？が連続しているようです。この基本値にバンドごとに固有の定数（これはビューアからコピペしたので ミスってるかも）をかけて足すと、ビューアのradianceと一致しました。
というわけで適当にお役立てください。また、私はまったく詳しくない人なので間違っているかもしれないです（間違っていたら教えてください、そしてごめんなさい）。
from math import * import os.path import struct import sys from PIL import Image def rgb(minimum, maximum, value): minimum, maximum = float(minimum), float(maximum) ratio = 2 * (value - minimum) / (maximum - minimum) b = int(max(0, 255 * (1 - ratio))) r = int(max(0, 255 * (ratio - 1))) g = 255 - b - r return r, g, b all_scale_factor_and_add_offset = [ (0.8121064, -25.936647), (0.15859237, -20.289911), (0.37691253, -12.037643), (0.07073108, -4.5223684), (0.09580004, -3.0596137), (0.030088475, -0.9609507), (0.001564351, -0.0376), (0.007104763, -0.5586), (0.022539102, -0.8236), (0.02004128, -0.9561), (0.03335779, -1.3022), (0.05443998, -1.5394), (0.04572892, -1.6443), (0.049492206, -1.7187), (0.05277411, -1.7558), (0.17605852, -5.2392), ] file = sys.argv[1] band = int(os.path.basename(file)[19:21]) scale_factor = all_scale_factor_and_add_offset[band - 1][0] add_offset = all_scale_factor_and_add_offset[band - 1][1] scale = int(sqrt(os.path.getsize(file) / 7500000)) width = 2500 * scale height = 1500 * scale radiances = [[0 for _ in range(width)] for _ in range(height)] min_radiance = 1e9 max_radiance = -1e9 with open(file, 'rb') as f: for i in range(width * height): x = i % width y = i // width p = struct.unpack('H', f.read(2))[0] radiance = p * scale_factor + add_offset radiances[y][x] = radiance min_radiance = min(min_radiance, radiance) max_radiance = max(max_radiance, radiance) image = Image.new('RGB', (width, height)) data = image.load() for y, rs in enumerate(radiances): for x, r in enumerate(rs): data[x, y] = rgb(min_radiance, max_radiance, r) image.save(file[:-3] + 'png')
北大日立マラソン第１回
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; }
WindowsでPython2/3の共存が壊れたらPYTHONHOMEを削除する
Windowsではpyとpy -2でPython2/3の共存ができますが、再インストールやマイナーバージョンのアップグレードなどで以下のように壊れることがあります。
>py
Fatal Python error: Py_Initialize: unable to load the file system codec
File "C:\python27\lib\encodings\__init__.py", line 123
raise CodecRegistryError,\
^
SyntaxError: invalid syntax
Current thread 0x00000e1c (most recent call first):
>py -2
File "C:\Python36\lib\site.py", line 177
file=sys.stderr)
^
SyntaxError: invalid syntax
これらは環境変数のPYTHONHOMEを削除すると直りました。このPYTHONHOMEはPython2/3の両方から参照されるらしく、削除するとそれぞれのデフォルト値が使われうまく動くようになるようです。
もしPythonをデフォルトのパス以外にインストールしている場合、さらに何らかのケアが必要かもしれません。
MM94 ConnectedComponent
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678
基本方針
順列の左端Ｎ個が確定しているとすると順列の後ろにどんな値を足しても左上Ｎ×Ｎの領域の値は変わらない。なのでこの確定領域の最良コンポーネントのスコアを途中状態のスコアとできる。
そして現在の順列の後ろに値を足して一番途中スコアが大きくなるような順列を次の状態とするgreedy/beamsearchをすると最良コンポーネントが徐々に大きくなり良い解が得られる。
高速化
途中スコアの愚直な計算はO(S2)であるためgreedyですら終わらないが、新しく足す値によって確定するマス（下図赤マス）と接するマス（下図緑マス）は現確定領域の"外周に限られる"ことを利用して差分計算/更新ができ高速になる。
具体的には緑マスそれぞれをノードとしたUnionFind（各ノードはそのマスが属すコンポーネントのsizeとsumを持つ）を現状態として持つ。次に緑UFを元に緑赤UFを作る。次に連結箇所をuf.unite()。最後に赤だけのUFを作ればそれが次状態になる。このとき連結を調べているのが外周付近だけであるためO(S2)がO(S)に落ちてgreedy/beamsearchが実行時間に収まる。また、UFを舐めればsumとsizeを持っているため最良コンポーネントとそのスコアがわかる。
このUnionFindを使って連結情報を右に右に伝えていくというのはこの問題でも使われてるっぽい。 http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2017%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=H.pdf
ビーム幅
同じseedで繰り返し実行したときのスコアの分散が大きめだったので、ビーム幅の増加によるスコア上昇よりも、細いビーム幅で繰り返したときの当たる確立の上昇のほうが強いと踏んで、ビーム幅1のビームサーチを時間いっぱい繰り返した。だけど1stと2ndは大きなビーム幅で1回ビームサーチらしいので外したっぽい。分散が大きいというのが違うのか、分散が大きいときは～のほうが強いというのが違うのか。
評価関数
最良コンポーネントの近くに他のコンポーネントがあって繋がると大きなスコアのプラスになるとき積極的に繋がりにいきたい。
これを評価関数に加える。他のコンポーネントはsumが大きいほど、sizeが大きいほど、近いほど（繋がりやすいことと連結に近づくため）良いとしたい。なので最良ではないコンポーネントそれぞれに対して、仮に最良コンポーネントと繋がったときのスコアの上昇量にpow(0.9, 最短距離)をかけたものを途中スコアに足した。
文章だとわかりづらいので擬似コード
double maxComponentScore = maxComponent.sum * sqrt(maxComponent.size); double score = maxComponentScore; for (auto& c : nonmaxComponents) { double connectedScore = (maxComponent.sum + c.sum) * sqrt(maxComponent.size + c.size); double diff = connectedScore - maxComponentScore; if (diff > 0) score += diff * pow(0.9, manhattanDistanceNearest(c, maxComponent)); } score; // これがビームサーチの評価値として使われる
1st, 2nd, 3rdまでの評価関数のプラスアルファがバラバラなのおもろい。
山登り
Sがごく小さいときはビームサーチの結果を山登り。ランダム解から登るより、ビームサーチからのほうが良かった。近傍は2つをswapと、1つを別のところにinsert(つまりrotate)の2種類。左上からビームサーチする都合、左上が高密度のコンポーネントができるので左上へのinsertで改善しやすかった。なのでその近傍を先んじて試すようにした。2つの近傍自体に優劣はないと思うんだけど、初期解が影響して優劣が生まれるというのがおもしろかった。
評価関数はO(S2)だがy_kawanoさんがchokudai contest（本問題と似ていて連結数を大きくする問題）で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝
得点計算の高速化はDFSの基点となる位置をキャッシュしたのが効いた #chokudai_003
— y_kawano (@y_kawano) 2017年2月21日
やりたかったけどできなかったこと
非0マスの割合によって連結の容易さがテストケースごとにかなり変わる。最終コンポーネントがスッカスカだったりミッチミチだったり。この特徴に注目して何かヒューリスティクスを刺したかった。
Example scores:
0) 232.826115373684 1) 23147.483599734984 2) 7426823.502824272 3) 121935.2517568238 4) 148933.58515123444 5) 2259336.504998536 6) 733271.118536657 7) 3257617.5326836635 8) 4670802.284891322 9) 1676018.7939363925
Image
seed=2, score=21907 pic.twitter.com/iIdLh9hhtg
— hakomo (@hakomof) 2017年8月24日
seed=3, score=7488480 pic.twitter.com/sYuESDhLFf
— hakomo (@hakomof) 2017年8月24日
seed=7, score=726365 pic.twitter.com/oJEr6GoE1l
— hakomo (@hakomof) 2017年8月24日
TCO17MMR2 AbstractWars
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16928&pm=14599
ヒューリスティクス的なアイデアが色々考えられて今までで一番好きな問題。
MMおつかれさまでした
— hakomo (@hakomof) 2017年5月25日
ビームサーチで速攻、序盤に奪う基地の探索
中終盤は1000をあふれるなら攻撃、攻撃箇所は最小費用流で決定
ビームサーチと最小費用流の評価関数は敵が同士討ちをしやすいほど良い
勝89.9% 負6.3% 分3.8%
— hakomo (@hakomof) 2017年5月25日
速攻は21.6% 速攻がtomerunさんの半分以下だ・・・
本当はもっとたくさん書いたんだけど長くなったのでがんばったところだけ。
以下抜粋。
敵同士をつぶしあわせる、ビームサーチの評価関数、最小費用流のコスト
自分が攻撃される確率が低いほどよい
初期配置を↓とする。
テキトーに近い敵baseを奪うと↓のようになり、これは敵自入り混じった乱戦になりpowerが不利な自分が負ける。
しかし↓のように敵baseを奪うと敵は距離の近いbaseを攻撃する確率が高いため自分をあまり攻撃せず敵同士でつぶしあってくれる。その間にsizeを着々と貯めれば100の倍数ボーナスで差がつくので勝てる。
このような自分が攻撃される確率が低い（相対的に敵同士でつぶしあいやすい）配置になるように敵を攻撃する。
敵の初撃に耐えるほどよい
序盤、敵baseを奪いすぎるとsizeが小さいため簡単に再奪取されることが多い。これを軽減するために奪えなかった敵base近くの自baseのsizeを大きくしたい。
localityを1.1とすると敵baseが各baseを攻撃する確率は計算できてattackTも決めれば初撃ターン・初撃サイズも求まり、自baseが奪われる確率も計算できる。そこでattackTの値域から均等に3つ583,750,917を選びその平均を初撃に耐える確率としそれが高いほどよいとした。
これで奪いすぎるのを軽減したり、敵baseの近くに壁をつくる効果が期待できる。
ビームサーチの評価関数
ビームサーチの評価関数 = 奪ったbaseの数 - 自分が攻撃される確率の和 - 敵の初撃で奪われる確率の和
狙ったわけではないが、自分が攻撃される確率が長期的な評価値で、敵の初撃で奪われる確率が短期的な評価値で、バランスがよさそう。
攻撃されやすい敵baseを攻撃するのは後回し
↓のような状況のとき上真ん中を奪うと左右からぼこされて再奪取されやすい。
しかし↓のように上右から奪うと真ん中の攻撃は左右に分散しやすく、左の攻撃は真ん中にいきやすい。そのため奪った後も守りやすい。
このように攻撃されやすい敵baseは奪った後も攻撃にさらされやすいので後回しにする。また攻撃されて弱った後なら楽に奪えるという効果もある。
最小費用流のコスト
最小費用流のコスト = 到着時刻 + 50 * -log(その敵baseが自分を攻撃する確率) + 40 * -log(max(1e-9, 1 - その敵baseが他の敵に攻撃される確率の和))
空を飛んでいるtroopはbaseと接触してはじめて効果がでる（敵baseを奪うにしろ、自baseに合流して100の倍数ボーナスを増やすにしろ、敵baseを削って100の倍数ボーナスを減らすにしろ）ので滞空時間、到着時刻は短いほうがよい。ので到着時刻にペナルティを加算した。
Example scores
0) 1700.3533398049744 1) 1806.7049780062375 2) 1978.8025098890039 3) 1962.538169965643 4) 1983.4413356595355 5) 1663.3656903521724 6) 1829.6786713895922 7) 1486.8174209242056 8) 1690.0970680903945 9) 1810.6962420903901
GIF
— hakomo (@hakomof) 2017年5月25日
— hakomo (@hakomof) 2017年5月25日
劣勢のときはまとまった数が残ってるうちに最遠２点間を往復する（これで２０００ターン逃げ切ることもある） pic.twitter.com/7IrIc1I4Fe
— hakomo (@hakomof) 2017年5月25日
Chokudai Contest 3 考えたこと
問題文 A: ○×ブロック - Chokudai Contest 003 | AtCoder
5864点18位でした。
. + -ブロックひとつを異なる種類の. + -ブロックに変えてスコアが上がるようなら保持、下がるようなら元に戻す山登りをした。
遷移でスコアが変わらなくても、連結ブロック数の２乗和が大きくなるときは遷移した（スコアに関係ない連結ブロックが成長したら良さそう）
上下にoとoもしくはxとxで挟まれた空間にはブロックを新設しない方がよさそうだった。連結を分断しやすそうなので。ただ間に合わなかったので確かめてない。
下の方からブロックを変えていくというのを２周した。
ブロックを変更していない列の落下処理はキャッシュして省略することで高速化（差分計算）、元に戻るときの情報を残しておいて元に戻すのを高速化などをして、試行回数は２２万回くらいだった。
ブロックは落下するので下の方にかたよる。なので落下しない-ブロックを上の方に置くのはよくない。なのでそもそも遷移を試さない。
むずかしかったー
