第2回 RCO日本橋ハーフマラソン 予選: B - ゲーム実況者Xのデフラグ

,

https://rco-contest-2018-qual.contest.atcoder.jp/tasks/rco_contest_2018_qual_b

Aと違ってBはだめで$48$位。 総合順位の付け方が「問題Aでの順位$\times$問題Bでの順位」に変更になってなかったら通過が怪しかった。運が良い。

solution

焼き鈍し ($310000$点)

ランダムに$2$点選んで、swapした場合の点数が$t$以下なら採用。 この$t$を時間と共に下げていく。

焼き鈍しのつもりはまったくなかったが、解説書くために見直すと完全に焼き鈍しだった。 文脈の強い問題を焼き鈍すテクとして覚えておきたい。 でもこれをするぐらいならビームサーチでよさそう。

上位者の解法のメモ

$1$位の解法:

chokudaiさんのDP方針 (バグ埋めなければ$1$位だったらしい):

この手の「分割して個別にDP」するタイプの解法を思い付けた試しがないが、典型テクとして初手で検討するようにした方がよさそう。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;

constexpr int h = 200;
constexpr int w = 200;
constexpr int d = 16000;
constexpr int k = 4000;
bool is_on_field(int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; }

struct point_t {
    int y, x;
};
inline int get_distance(point_t a, point_t b) {
    return abs(b.y - a.y) + abs(b.x - a.x);
}

int calculate_cost(vector<int> const & row, vector<int> const & col, deque<pair<point_t, point_t> > const & swaps) {
    array<array<point_t, w>, h> sector;
    REP (y, h) REP (x, w) sector[y][x] = { y, x };
    REP_R (i, int(swaps.size())) {
        point_t a, b; tie(a, b) = swaps[i];
        swap(sector[a.y][a.x], sector[b.y][b.x]);
    }
    int cost = 0;
    REP (i, d - 1) {
        cost += get_distance(sector[row[i + 1]][col[i + 1]], sector[row[i]][col[i]]);
    }
    return cost;
}

int main() {
    chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now();

    // input
    { string s; getline(cin, s); }
    vector<int> original_row(d), original_col(d);
    REP (i, d) cin >> original_row[i] >> original_col[i];

    // solve
    default_random_engine gen;
    int lowest_cost = INT_MAX;
    deque<pair<point_t, point_t> > result;

    for (int iteration = 0; ; ++ iteration) {
        chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now();
        if (chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() >= 3000) break;

        auto row = original_row;
        auto col = original_col;
        deque<pair<point_t, point_t> > swaps;
        array<array<int, w>, h> data;
        REP (y, h) REP (x, w) data[y][x] = -1;
        REP (i, d) {
            data[row[i]][col[i]] = i;
        }

        for (int limit = 1600; limit >= 10; limit -= (limit >= 1000 ? 100 : 5)) {
            REP (iteration, 100000) {
                {
                    int i = uniform_int_distribution<int>(1, d - 2)(gen);
                    int j = i;
                    while (abs(i - j) <= 3 or (i <= 3 and d - 3 < j)) {
                        j = uniform_int_distribution<int>(1, d - 2)(gen);
                    }

                    int delta = 0;
                    delta -= abs(row[i] - row[i - 1]);
                    delta -= abs(col[i] - col[i - 1]);
                    delta -= abs(row[i + 1] - row[i]);
                    delta -= abs(col[i + 1] - col[i]);
                    delta -= abs(row[j] - row[j - 1]);
                    delta -= abs(col[j] - col[j - 1]);
                    delta -= abs(row[j + 1] - row[j]);
                    delta -= abs(col[j + 1] - col[j]);

                    swap(data[row[i]][col[i]], data[row[j]][col[j]]);
                    swap(row[i], row[j]);
                    swap(col[i], col[j]);

                    delta += abs(row[i] - row[i - 1]);
                    delta += abs(col[i] - col[i - 1]);
                    delta += abs(row[i + 1] - row[i]);
                    delta += abs(col[i + 1] - col[i]);
                    delta += abs(row[j] - row[j - 1]);
                    delta += abs(col[j] - col[j - 1]);
                    delta += abs(row[j + 1] - row[j]);
                    delta += abs(col[j + 1] - col[j]);

                    if (delta < - limit) {
                        swaps.emplace_front((point_t) { row[i], col[i] }, (point_t) { row[j], col[j] });
                        if (swaps.size() == k) break;
                    } else {
                        swap(col[i], col[j]);
                        swap(row[i], row[j]);
                        swap(data[row[i]][col[i]], data[row[j]][col[j]]);
                    }
                }
                {
                    int i = uniform_int_distribution<int>(1, d - 2)(gen);
                    int y = row[i];
                    int x = col[i];
                    while (data[y][x] != -1) {
                        y = uniform_int_distribution<int>(0, h - 1)(gen);
                        x = uniform_int_distribution<int>(0, w - 1)(gen);
                    }

                    int delta = 0;
                    delta -= abs(row[i] - row[i - 1]);
                    delta -= abs(col[i] - col[i - 1]);
                    delta -= abs(row[i + 1] - row[i]);
                    delta -= abs(col[i + 1] - col[i]);

                    swap(data[row[i]][col[i]], data[y][x]);
                    swap(row[i], y);
                    swap(col[i], x);

                    delta += abs(row[i] - row[i - 1]);
                    delta += abs(col[i] - col[i - 1]);
                    delta += abs(row[i + 1] - row[i]);
                    delta += abs(col[i + 1] - col[i]);

                    if (delta < - limit) {
                        swaps.emplace_front((point_t) { row[i], col[i] }, (point_t) { y, x });
                        if (swaps.size() == k) break;
                    } else {
                        swap(col[i], x);
                        swap(row[i], y);
                        swap(data[row[i]][col[i]], data[y][x]);
                    }
                }
            }
            if (swaps.size() == k) break;
        }

        int cost = calculate_cost(original_row, original_col, swaps);
        if (cost < lowest_cost) {
            lowest_cost = cost;
            result = swaps;
        }
break;
    }

    // output
    for (auto swp : result) {
        cout << swp.first.y << ' ' << swp.first.x << ' ' << swp.second.y << ' ' << swp.second.x << ' '  << endl;
    }
    return 0;
}