びったんびったん

ユーザビリティ・プログラミングについて。

Topcoder Marathon Match 100 SameColorPairs

問題文

方針

私は焼きなまし厨なのでとりあえず焼きなましを考えます。

この問題の要求する解は消すペアとその順番です。その解そのものを(順番を含めて)直接焼きなますというのは難しそうです。なぜならあるペアを消すと新たにペアが消せるようになる、といった順序関係が強そうなので、順番を安易に変えると状態が壊れそうだからです。

そこで消すペアと順番を分けて考えてみます。消すペアの集合(消せる消せないにかかわらずすべてのマスをペアにしたもの)を固定したときの順番はどうなるでしょうか。これは以下のような簡単な貪欲で最適な順番、最適なスコアが求まります。

  1. 消せるペアを消す
  2. 新たに消せるペアが増えるのでそれも消す
  3. 1つも消せなくなるまで消す

なので、

  • 消すペアの集合を焼きなましの状態とする
  • 状態を少し変えたら、先の貪欲でスコア(差)を求めて遷移判定をする

とすれば焼きなましに帰着できました!

近傍

同じ色のペアを2つ選んでつなぎかえます。マスAとBを消すペアとマスCとDを消すペアを、ACを消すペアとBDを消すペアに変えるといった感じです。

状態に制限がなく、近傍も小さいのでうまく焼きなませそうです。

ですが、先の貪欲はめちゃくちゃ遅いのでまともにまわりません。なので収束速度の底上げ・高速化をしていきます。

盤面を分割して順に焼きなまします。探索空間が小さくなり収束が速くなることが期待されます。消すペアは近いことが多いので局所的な焼きなましはあまりデメリットになりませんでした。

盤面は1-27分割しますが最後の2ブロックだけ多スタートします。

近傍は、消せないペアか他のペアをたくさん囲っているペアの中から選びます。他のペアをたくさん囲っているペアというのは、囲われているペアが先に消えることを縛っていて、それがたくさんということは大局的に良い状態ではない可能性があります。なので変更の候補です。

近傍のつなぎかえ先は(広義)近いマスほど高確率で選ばれるようにします。

先の貪欲は次のような言い換えができます。消すペアを頂点として、ぺアXを消してからでないとペアYを消せないときXからYに有向辺を張った依存グラフを、閉路の手前までトポロジカルソートすると先の貪欲と同じ結果が得られます。消せるペアを探す手間が省ける分こっちのほうがたぶん速いです。

評価値は、消せるペア数 - 依存グラフの最小閉路の数 / 2.5です。閉路以下のペアはすべて死ぬので閉路の数をペナルティとすると探索空間がなだらかになってよさげです。

依存グラフは差分更新します。更新が必要な辺は、変更する2つのペアに入出する辺だけなので、グラフ全体を毎回つくりなおさなくていいです。

依存グラフを差分更新するにあたり、新しいペアを囲うペアを列挙する必要がありますが、愚直にすべてのペアを走査すると遅いので、バイナリ空間分割という衝突している物体の列挙を高速にするアルゴリズムを使います。囲われていることと衝突していることは同じことなので転用できます。

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点ぐらい

入力バイナリから画像を作成するプログラムを公開しました

圧縮する入力バイナリは2次元のradianceのデータなようです。 このデータの画像はnetCDFデータのビューアから見ることができるようで、見るためにはnetCDFデータをビューアで開く、Rad行をダブルクリック、Create a 2D plotを選択します。

f:id:hakomof:20171216003749p:plain

とりあえず入力バイナリがどんなものか理解するために、入力バイナリから同じ画像を作成するプログラムを書きました。動作にはPython3、ライブラリPillowが必要です。(ソースコードはブログ最下部)

py script.py bin_4obs/OR_ABI-L1b-RadC-M3C01_G16_s20172101802185_e20172101804558_c20172101805000.bin

f:id:hakomof:20171216003715p:plain

これで画像が作成されます。色がぜんぜん違いますが、グラデーション色が違うだけでradianceはビューアと一致しています。

入力バイナリは、2次元を1次元につぶした2バイトの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')

北大日立マラソン第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、白線が近傍

f:id:hakomof:20171130175210g:plain

↑最初から最後までのダイジェスト(飛び飛び)。

  • 存外ふらふらするので初期解は中央にかためてランダム(壁にひっつくと遷移の自由度が下がって良くないので
  • 良い解は円に近そうに見える(正方形や長方形よりも円のほうが辺数が多いことは確認した(yowaさんのtweetによると正八角形が最大らしい?
  • 良い解は赤い(得点をもらえる辺はWeightが大きい辺に偏る)。ので近傍を一様ランダムセレクトではなく、round(sqrt(Weight))で重み付けランダムセレクトした

f:id:hakomof:20171130175401g:plain

↑真ん中らへんの遷移を連続で

  • 実際の遷移(白線)はかたまりの端と端が多い(かたまりの内側を動かすとスコアが大きく下がりやすく、焼きなましの遷移確率はスコアが大きく下がるときは低いのでそれはそう)。なのでこれをうまく使おうとしたけど難しかった。

その他

  • 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ではpypy -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

基本方針

順列の左端N個が確定しているとすると順列の後ろにどんな値を足しても左上N×Nの領域の値は変わらない。なのでこの確定領域の最良コンポーネントのスコアを途中状態のスコアとできる。

f:id:hakomof:20170824194351p:plain

そして現在の順列の後ろに値を足して一番途中スコアが大きくなるような順列を次の状態とするgreedy/beamsearchをすると最良コンポーネントが徐々に大きくなり良い解が得られる。

高速化

途中スコアの愚直な計算はO(S2)であるためgreedyですら終わらないが、新しく足す値によって確定するマス(下図赤マス)と接するマス(下図緑マス)は現確定領域の"外周に限られる"ことを利用して差分計算/更新ができ高速になる。

f:id:hakomof:20170824194401p:plain

具体的には緑マスそれぞれをノードとした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回ビームサーチらしいので外したっぽい。分散が大きいというのが違うのか、分散が大きいときは~のほうが強いというのが違うのか。

評価関数

最良コンポーネントの近くに他のコンポーネントがあって繋がると大きなスコアのプラスになるとき積極的に繋がりにいきたい。

f:id:hakomof:20170824194416p:plain

これを評価関数に加える。他のコンポーネントは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(本問題と似ていて連結数を大きくする問題)で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝

やりたかったけどできなかったこと

非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

TCO17MMR2 AbstractWars

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16928&pm=14599

ヒューリスティクス的なアイデアが色々考えられて今までで一番好きな問題。

本当はもっとたくさん書いたんだけど長くなったのでがんばったところだけ。
以下抜粋。

敵同士をつぶしあわせる、ビームサーチの評価関数、最小費用流のコスト

自分が攻撃される確率が低いほどよい

初期配置を↓とする。

f:id:hakomof:20170525230804p:plain

テキトーに近い敵baseを奪うと↓のようになり、これは敵自入り混じった乱戦になりpowerが不利な自分が負ける。

f:id:hakomof:20170525230818p:plain

しかし↓のように敵baseを奪うと敵は距離の近いbaseを攻撃する確率が高いため自分をあまり攻撃せず敵同士でつぶしあってくれる。その間にsizeを着々と貯めれば100の倍数ボーナスで差がつくので勝てる。

f:id:hakomof:20170525230836p:plain

このような自分が攻撃される確率が低い(相対的に敵同士でつぶしあいやすい)配置になるように敵を攻撃する。

敵の初撃に耐えるほどよい

序盤、敵baseを奪いすぎるとsizeが小さいため簡単に再奪取されることが多い。これを軽減するために奪えなかった敵base近くの自baseのsizeを大きくしたい。

f:id:hakomof:20170525230847p:plain

localityを1.1とすると敵baseが各baseを攻撃する確率は計算できてattackTも決めれば初撃ターン・初撃サイズも求まり、自baseが奪われる確率も計算できる。そこでattackTの値域から均等に3つ583,750,917を選びその平均を初撃に耐える確率としそれが高いほどよいとした。

これで奪いすぎるのを軽減したり、敵baseの近くに壁をつくる効果が期待できる。

ビームサーチの評価関数

ビームサーチの評価関数 = 奪ったbaseの数 - 自分が攻撃される確率の和 - 敵の初撃で奪われる確率の和

狙ったわけではないが、自分が攻撃される確率が長期的な評価値で、敵の初撃で奪われる確率が短期的な評価値で、バランスがよさそう。

攻撃されやすい敵baseを攻撃するのは後回し

↓のような状況のとき上真ん中を奪うと左右からぼこされて再奪取されやすい。

f:id:hakomof:20170525230857p:plain

しかし↓のように上右から奪うと真ん中の攻撃は左右に分散しやすく、左の攻撃は真ん中にいきやすい。そのため奪った後も守りやすい。

f:id:hakomof:20170525230902p:plain

このように攻撃されやすい敵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