提出 #54642266

---

ソースコード 拡げる

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print1(){print0("\n");}; template<typename H,typename... T>void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);}
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }
using pii = pair<int,int>;
const int inf = 1e9;
// clang-format on
namespace marathon {
mt19937 engine(0);
clock_t start_time;
double now() {
    return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
    start_time = clock();
    random_device seed_gen;
    engine.seed(seed_gen());
}
int randint(int mn, int mx) {
    int rng = mx - mn + 1;
    return mn + (engine() % rng);
}
double uniform(double x, double y) {
    const int RND = 1e8;
    double mean = (x + y) / 2.0;
    double dif = y - mean;
    double p = double(engine() % RND) / RND;
    return mean + dif * (1.0 - 2.0 * p);
}
template <typename T>
T random_choice(vector<T> &vec) {
    return vec[engine() % vec.size()];
}
bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
    const int ANNEAL_RND = 1e8;
    const double ANNEAL_EPS = 1e-6;
    double temp = (begin_temp * (end_time - cur_time) + end_temp * (cur_time - begin_time)) / (end_time - begin_time);
    return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}
bool anneal_accept2(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
    static int called = 0;
    static double temp = 0;
    if ((called & 127) == 0) {
        double ratio = (cur_time - begin_time) / (end_time - begin_time);
        ratio = min(ratio, 1.0);
        temp = pow(begin_temp, 1.0 - ratio) * pow(end_temp, ratio);
    }
    called++;

    const int ANNEAL_RND = 1e8;
    const double ANNEAL_EPS = 1e-6;

    return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}

}  // namespace marathon
const int N = 20;
const int N2 = 400;
int INIT_H[N2];
int distance_table[N2][N2];
vector<int> near_minuses[N2];
vector<int> near_pluses[N2];
vector<int> nexts[N2];
struct state_t {
    int p;
    int d;
    int h[N2];
    state_t() {
        p = 0;
        d = 0;
        for (int u = 0; u < N2; u++) {
            h[u] = INIT_H[u];
        }
    }
};
void output(vector<int> ops) {
    auto pts2char = [](int a, int b) {
        int ar = a / N;
        int ac = a % N;
        int br = b / N;
        int bc = b % N;
        if (br > ar) return 'D';
        if (br < ar) return 'U';
        if (bc > ac) return 'R';
        if (bc < ac) return 'L';
        return '.';
    };
    int now = 0;
    for (auto op : ops) {
        if (op >= inf / 2) {
            int s = op - inf;
            if (s > 0) {
                cout << "+" << s << endl;
            } else {
                cout << s << endl;
            }

        } else {
            cout << pts2char(now, op) << endl;
            now = op;
        }
    }
}
vector<pii> greedy2(vector<int> plus) {
    state_t state;
    state.p = 0;
    state.d = 0;
    for (int u = 0; u < N2; u++) {
        state.h[u] = INIT_H[u];
    }
    vector<pii> ops;
    for (int pi = 0; pi < int(plus.size()); pi++) {
        int pcnt = plus[pi];
        while (true) {
            pcnt--;
            pii near_minus = {inf, -1};
            if (pcnt < 0 && state.d > 0) {
                for (auto u : near_minuses[state.p]) {
                    if (state.h[u] < 0) {
                        near_minus = {distance_table[state.p][u], u};
                        break;
                    }
                }
            }
            pii near_plus = {inf, -1};
            if (pcnt >= 0) {
                for (auto u : near_pluses[state.p]) {
                    if (state.h[u] > 0) {
                        near_plus = {distance_table[state.p][u], u};
                        break;
                    }
                }
            }
            if (near_minus.first == inf && near_plus.first == inf) break;
            int dest = min(near_minus, near_plus).second;

            if (state.h[dest] > 0) {
                int getsand = state.h[dest];
                state.d += getsand;
                state.h[dest] -= getsand;
                ops.push_back({dest, getsand});
            } else {
                int putsand = min(state.d, abs(state.h[dest]));
                state.d -= putsand;
                state.h[dest] += putsand;
                ops.push_back({dest, -putsand});
            }
            state.p = dest;
        }
    }
    return ops;
}
double greedy1(vector<int> plus) {
    state_t state;
    state.p = 0;
    state.d = 0;
    for (int u = 0; u < N2; u++) {
        state.h[u] = INIT_H[u];
    }
    vector<int> ops;
    int cost = 0;
    for (int pi = 0; pi < int(plus.size()); pi++) {
        int pcnt = plus[pi];
        while (true) {
            pcnt--;
            pii near_minus = {inf, -1};
            if (pcnt < 0 && state.d > 0) {
                for (auto u : near_minuses[state.p]) {
                    if (state.h[u] < 0) {
                        near_minus = {distance_table[state.p][u], u};
                        break;
                    }
                }
            }
            pii near_plus = {inf, -1};
            if (pcnt >= 0) {
                for (auto u : near_pluses[state.p]) {
                    if (state.h[u] > 0) {
                        near_plus = {distance_table[state.p][u], u};
                        break;
                    }
                }
            }
            if (near_minus.first == inf && near_plus.first == inf) break;
            int dest = min(near_minus, near_plus).second;
            cost += (state.d + 100) * distance_table[state.p][dest];
            if (state.h[dest] > 0) {
                int getsand = state.h[dest];
                state.d += getsand;
                state.h[dest] -= getsand;
                cost += abs(getsand);
            } else {
                int putsand = min(state.d, abs(state.h[dest]));
                state.d -= putsand;
                state.h[dest] += putsand;
                cost += abs(putsand);
            }
            state.p = dest;
        }
    }
    // return 1.0 / cost;
    return -cost;
}

struct range_t {
    int d;
    int si;
    int ti;
};
vector<pii> small_ops_bf(vector<pii> initial_ops) {
    // 積みの連続、降ろしの連続になっている区間ごとに、全探索で順番を決める
    // 降ろしについては、降ろす土砂のサイズも保存する
    vector<range_t> ranges;
    {
        int d = 0;

        for (int i = 0; i < initial_ops.size(); i++) {
            auto op = initial_ops[i];
            d += op.second;
            assert(d >= 0);
            if (ranges.size() && initial_ops[ranges.back().si].second * op.second > 0) {  // 符号が同じ
                ranges.back().ti = i;
            } else {
                ranges.push_back({d, i, i});
            }
        }
    }
    auto get_oi = [&](int ri, int u) {
        return u + ranges[ri].si;
    };
    auto get_p = [&](int ri, int u) {
        return initial_ops[u + ranges[ri].si].first;
    };
    auto get_d = [&](int ri, int u) {
        return initial_ops[u + ranges[ri].si].second;
    };
    auto calc_score = [&](vector<pii> ops) {
        int m = ops.size();
        int p = 0;
        int d = 0;
        int cost = 0;
        for (auto op : ops) {
            cost += (d + 100) * distance_table[p][op.first];
            d += op.second;
            p = op.first;
        }
        return -cost;
    };

    auto ops = initial_ops;
    double old_score = calc_score(ops);
    pair<double, vector<pii>> best = {old_score, ops};
    double ini_score = old_score;
    double end_time = 1900;
    double begin_time = marathon::now();

    int anneal_iter = 0;
    int anneal_accepted = 0;

    double begin_temp = 200;
    double end_temp = 20;
    while (marathon::now() < end_time) {
        int ri = marathon::engine() % ranges.size();
        if (ranges[ri].ti == ranges[ri].si) continue;

        anneal_iter++;
        if (anneal_iter % 10000 == 0) {
            ops = best.second;
            old_score = best.first;
        }
        int s = 0;
        int t = 0;
        while (s == t) {
            s = marathon::randint(ranges[ri].si, ranges[ri].ti);
            t = marathon::randint(ranges[ri].si, ranges[ri].ti);
        }
        swap(ops[s], ops[t]);
        double new_score = calc_score(ops);
        if (marathon::anneal_accept2(new_score, old_score, marathon::now(), begin_time, end_time, begin_temp, end_temp)) {
            anneal_accepted++;
            if (anneal_accepted % 1000 == 0) debug4(new_score, old_score, anneal_iter, anneal_accepted);
            old_score = new_score;
            if (best.first < old_score) {
                best = {old_score, ops};
            }
        } else {
            swap(ops[s], ops[t]);
        }
    }
    debug2(anneal_iter, anneal_accepted);
    debug2(int(round(abs(1e9 / ini_score))), int(round(abs(1e9 / best.first))));
    return best.second;
}
vector<int> anneal(vector<int> initial_ans) {
    // 積みの回数を焼く
    vector<int> plus;
    {
        int pt = 0;
        vector<int> route;
        for (int op : initial_ans) {
            if (op >= inf / 2) {
                route.push_back(pt);
            } else {
                pt = op;
            }
        }

        int m = route.size();
        for (int i = 0; i < m; i++) {
            if (INIT_H[route[i]] > 0) {
                if (plus.size() && INIT_H[route[i - 1]] > 0) {
                    plus.back()++;
                } else {
                    plus.push_back(1);
                }
            }
        }
    }
    double end_time = 1400;
    double begin_time = marathon::now();

    double old_score = greedy1(plus);

    int anneal_iter = 0;
    int anneal_accepted = 0;

    double begin_temp = 2000;
    double end_temp = 20;
    pair<double, vector<int>> bestplus = {old_score, plus};
    while (marathon::now() < end_time) {
        anneal_iter++;
        if (anneal_iter % 6000 == 0) {
            old_score = bestplus.first;
            plus = bestplus.second;
        }
        int ran = marathon::engine() % 100;
        if (ran < 90) {
            int x = 0;
            int y = 0;
            while (x == y) {
                x = marathon::engine() % plus.size();
                y = marathon::engine() % plus.size();
            }
            auto newplus = plus;
            int adds = marathon::randint(1, min(newplus[x], 2));
            newplus[x]--;
            newplus[y]++;
            if (newplus[x] == 0) {
                vector<int> tmp;
                for (auto e : newplus) {
                    if (e > 0) tmp.push_back(e);
                }
                newplus = tmp;
            }
            double new_score = greedy1(newplus);

            if (marathon::anneal_accept2(new_score, old_score, marathon::now(), begin_time, end_time, begin_temp, end_temp)) {
                anneal_accepted++;
                if (anneal_accepted % 200 == 0) debug2(new_score, old_score);
                plus = newplus;
                old_score = new_score;
                if (bestplus.first < old_score) {
                    bestplus = {old_score, plus};
                }
            }
        } else if (ran < 95) {
            if (plus.size() == 1) continue;
            int x = marathon::engine() % int(plus.size() - 1);

            vector<int> newplus;
            {
                for (int j = 0; j < int(plus.size()); j++) {
                    if (j == x) {
                        newplus.push_back(plus[j] + plus[j + 1]);
                        j++;
                    } else {
                        newplus.push_back(plus[j]);
                    }
                }
            }
            double new_score = greedy1(newplus);

            if (marathon::anneal_accept2(new_score, old_score, marathon::now(), begin_time, end_time, begin_temp, end_temp)) {
                // debug1("join");
                anneal_accepted++;
                if (anneal_accepted % 200 == 0) debug2(new_score, old_score);
                plus = newplus;
                old_score = new_score;
                if (bestplus.first < old_score) {
                    bestplus = {old_score, plus};
                }
            }
        } else {
            int x = 0;
            for (int it = 0; it < 1000; it++) {
                x = marathon::engine() % plus.size();
                if (plus[x] <= 1) continue;
                break;
            }
            if (plus[x] <= 1) continue;

            int spl = marathon::randint(1, plus[x] - 1);
            vector<int> newplus;
            {
                for (int j = 0; j < int(plus.size()); j++) {
                    if (j == x) {
                        newplus.push_back(spl);
                        newplus.push_back(plus[j] - spl);
                    } else {
                        newplus.push_back(plus[j]);
                    }
                }
            }
            double new_score = greedy1(newplus);

            if (marathon::anneal_accept2(new_score, old_score, marathon::now(), begin_time, end_time, begin_temp, end_temp)) {
                // debug1("split");
                anneal_accepted++;
                if (anneal_accepted % 200 == 0) debug2(new_score, old_score);
                plus = newplus;
                old_score = new_score;
                if (bestplus.first < old_score) {
                    bestplus = {old_score, plus};
                }
            }
        }
    }
    debug4(anneal_iter, anneal_accepted, old_score, abs(round(int(1e9 / old_score))));
    {
        auto route = small_ops_bf(greedy2(bestplus.second));
        vector<int> result;
        int m = route.size();
        int d = 0;
        vector<int> hs(N2);
        for (int u = 0; u < N2; u++) {
            hs[u] = INIT_H[u];
        }
        for (int i = 0; i < m; i++) {
            int src = 0;
            if (i > 0) {
                src = route[i - 1].first;
            }

            auto dest = route[i].first;
            while (src != dest) {
                for (auto nxt : nexts[src]) {
                    if (distance_table[src][dest] > distance_table[nxt][dest]) {
                        result.push_back(nxt);
                        src = nxt;
                        break;
                    }
                }
            }
            result.push_back(route[i].second + inf);
        }
        return result;
    }
}
void solve() {
    state_t state;
    state.p = 0;
    state.d = 0;
    for (int u = 0; u < N2; u++) {
        state.h[u] = INIT_H[u];
    }
    vector<int> ops;
    while (true) {
        pii near_minus = {inf, -1};
        if (state.d > 0) {
            for (int u = 0; u < N2; u++) {
                if (state.h[u] < 0) {
                    pii now = {distance_table[state.p][u], u};
                    near_minus = min(now, near_minus);
                }
            }
        }
        pii near_plus = {inf, -1};
        if (state.d < 200) {
            for (int u = 0; u < N2; u++) {
                if (state.h[u] > 0) {
                    pii now = {distance_table[state.p][u], u};
                    near_plus = min(now, near_plus);
                }
            }
        }
        if (near_minus.first == inf && near_plus.first == inf) break;
        int dest = min(near_minus, near_plus).second;
        while (dest != state.p) {
            for (auto nxt : nexts[state.p]) {
                if (distance_table[state.p][dest] > distance_table[nxt][dest]) {
                    ops.push_back(nxt);
                    state.p = nxt;
                    break;
                }
            }
        }
        if (state.h[dest] > 0) {
            int getsand = state.h[dest];
            state.d += getsand;
            state.h[dest] -= getsand;
            ops.push_back(getsand + inf);
        } else {
            int putsand = min(state.d, abs(state.h[dest]));
            state.d -= putsand;
            state.h[dest] += putsand;
            ops.push_back(-putsand + inf);
        }
    }
    output(anneal(ops));
}
int main() {
    marathon::marathon_init();
    int n;
    cin >> n;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> INIT_H[r * N + c];
        }
    }
    for (int u = 0; u < N2; u++) {
        for (int v = 0; v < N2; v++) {
            int ur = u / N;
            int uc = u % N;
            int vr = v / N;
            int vc = v % N;
            distance_table[u][v] = abs(ur - vr) + abs(uc - vc);
            if (distance_table[u][v] == 1) {
                nexts[u].push_back(v);
            }
        }
    }
    for (int u = 0; u < N2; u++) {
        vector<pair<int, int>> nm;
        for (int v = 0; v < N2; v++) {
            if (INIT_H[v] < 0) {
                nm.push_back({distance_table[u][v], v});
            }
        }
        sort(nm.begin(), nm.end());
        for (auto p : nm) {
            near_minuses[u].push_back(p.second);
        }
    }
    for (int u = 0; u < N2; u++) {
        vector<pair<int, int>> np;
        for (int v = 0; v < N2; v++) {
            if (INIT_H[v] > 0) {
                np.push_back({distance_table[u][v], v});
            }
        }
        sort(np.begin(), np.end());
        for (auto p : np) {
            near_pluses[u].push_back(p.second);
        }
    }

    solve();
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘std::vector<std::pair<int, int> > small_ops_bf(std::vector<std::pair<int, int> >)’:
Main.cpp:222:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  222 |         for (int i = 0; i < initial_ops.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:243:13: warning: unused variable ‘m’ [-Wunused-variable]
  243 |         int m = ops.size();
      |             ^
Main.cpp: In function ‘std::vector<std::pair<int, int> > small_ops_bf(std::vector<std::pair<int, int> >)’:
Main.cpp:233:10: warning: variable ‘get_oi’ set but not used [-Wunused-but-set-variable]
  233 |     auto get_oi = [&](int ri, int u) {
      |          ^~~~~~
Main.cpp:236:10: warning: variable ‘get_p’ set but not used [-Wunused-but-set-variable]
  236 |     auto get_p = [&](int ri, int u) {
      |          ^~~~~
Main.cpp:239:10: warning: variable ‘get_d’ set but not used [-Wunused-but-set-variable]
  239 |     auto get_d = [&](int ri, int u) {
      |          ^~~~~
Main.cpp: In function ‘std::vector<int> anneal(std::vector<int>)’:
Main.cpp:350:17: warning: unused variable ‘adds’ [-Wunused-variable]
  350 |             int adds = marathon::randint(1, min(newplus[x], 2));
      |                 ^~~~
Main.cpp:438:13: warning: unused variable ‘d’ [-Wunused-variable]
  438 |         int d = 0;
      |             ^

ジャッジ結果