びったんびったん

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

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

圧縮する入力バイナリは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

Chokudai Contest 3 考えたこと

問題文 A: ○×ブロック - Chokudai Contest 003 | AtCoder

5864点18位でした。

. + -ブロックひとつを異なる種類の. + -ブロックに変えてスコアが上がるようなら保持、下がるようなら元に戻す山登りをした。

遷移でスコアが変わらなくても、連結ブロック数の2乗和が大きくなるときは遷移した(スコアに関係ない連結ブロックが成長したら良さそう)

上下にooもしくはxxで挟まれた空間にはブロックを新設しない方がよさそうだった。連結を分断しやすそうなので。ただ間に合わなかったので確かめてない。

下の方からブロックを変えていくというのを2周した。

ブロックを変更していない列の落下処理はキャッシュして省略することで高速化(差分計算)、元に戻るときの情報を残しておいて元に戻すのを高速化などをして、試行回数は22万回くらいだった。

ブロックは落下するので下の方にかたよる。なので落下しない-ブロックを上の方に置くのはよくない。なのでそもそも遷移を試さない。

むずかしかったー

MM92 考えたこと

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

感想

CutTheRootsに高速化焼きなましって意味で似てるなー、CutTheRootsってたしか最上位厳密スコア求めてるんだよなーこれも厳密スコアかなーで突っ走った結果、近似スコアだったでござる。 初日で方針ミスって、しかも下手に良いスコアとってしまい方針ミスに気付けなかったので次からは気をつけたい。

自分の方針だと色んな箇所に色んな高速化をしていて高速化ゲー(もちろん高速化だけでは厳しいけど)としてはかなり楽しい(そして練習になる)問題だと思いました。(ただこの記事ではほとんど省略されてます)

焼きなまし

近傍はライトを1つ動かす。 焼きなまし序盤はライトを大きく動かして、終盤は小さく動かす。動かす距離は時間の経過とともに指数的に小さくした(試行回数の少なさを補うにはこれが良いと思った)。


壁の近くはすぐにライトがカットされるので良い位置ではないだろうと遷移しないようにしてみたがあまり効果なし。


遷移先に偏りのない605Kでるプログラムでinner_xとinner_y(小数点以下の座標)の分布を見ると、ものっそい偏ってた。

f:id:hakomof:20170119224502p:plain

ヒートマップの色はテキトーだけど光源の45%がinner_x == 0 || inner_y == 0だった。おそらくライトの半径が整数で壁も整数刻みなので、inner_x == 0 || inner_y == 0だと壁と壁の間にすっぽりぴったし収まりやすいのだと思われる。なのでinner_x == 0 || inner_y == 0に遷移しやすくしてみたのだけどあまり効果なし(がーん)。

山登り

CutTheRootsしかりTerrainCrossingしかり座標が広い問題は最後に極端に狭い近傍で山登りというのをみなさまやってらっしゃる。のでライトを1つ周囲8dotに動かす山登りを最後にした。

高速化

100dot x 100dot(1セル)をunsigned long long[100][2]の格ビットで表現する。

f:id:hakomof:20170119224504p:plain

放射光のビットパターンと円形の光のビットパターンのandビット演算をすれば1つのライトのビットパターンが求まる。ライトとライトのorビット演算をすればライトが重なったビットパターンが求まる。あとはビットの数を数えれば(__builtin_popcountll)厳密なスコアが求まる。

f:id:hakomof:20170119224506p:plain

円形の光のビットパターンは事前に計算して持ってくる。

放射光のビットパターンは、 まず、放射光の境界線の角度が、光源から外に向かって貰うDPで求まる。 次に、境界線の角度と光源の座標から境界線の直線の式が求まる。 そして、直線の式に求めたいビット列のy座標を代入すれば何ビット目から何ビット目まで立ってるかがわかるのでビット列を求める。

他の(でも重要な)高速化

あるセルをあるライトが完全に照らしているとき、他のライトの処理の省略、代替、遅延、枝刈による高速化(これが重要だけど説明できず)。

壁による遮蔽なしライトの重なりなしなセルのスコアは2次元累積和でO(1)で求まる。

差分計算もしてます(これも重要だけど説明できず)。