提出 #7232262

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#define dump(x) cerr << #x " = " << x << endl
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, (int)xs.size() - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }
template<typename Functor> struct fix_type { Functor functor; template<typename... Args> decltype(auto) operator() (Args && ... args) const & { return functor(functor, std::forward<Args>(args)...); } };
template<typename Functor> fix_type<typename std::decay<Functor>::type> fix(Functor && functor) { return { std::forward<Functor>(functor) }; }

class xor_shift_128 {
public:
    typedef uint32_t result_type;
    xor_shift_128(uint32_t seed = 42) {
        set_seed(seed);
    }
    void set_seed(uint32_t seed) {
        a = seed = 1812433253u * (seed ^ (seed >> 30));
        b = seed = 1812433253u * (seed ^ (seed >> 30)) + 1;
        c = seed = 1812433253u * (seed ^ (seed >> 30)) + 2;
        d = seed = 1812433253u * (seed ^ (seed >> 30)) + 3;
    }
    uint32_t operator() () {
        uint32_t t = (a ^ (a << 11));
        a = b; b = c; c = d;
        return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8));
    }
    static constexpr uint32_t max() { return numeric_limits<result_type>::max(); }
    static constexpr uint32_t min() { return numeric_limits<result_type>::min(); }
private:
    uint32_t a, b, c, d;
};

int compute_score(int n, array<int, 3> b, const vector<vector<int> > & a) {
    int score = 0;
    auto two_pointers = [&](auto && a) {
        array<int, 3> acc = {};
        array<int, 3> r = {};
        REP (l, n) {
            REP (i, 3) {
                if (l - 1 >= 0) {
                    acc[i] -= a(l - 1);
                }
                while (r[i] < n and acc[i] + a(r[i]) <= b[i]) {
                    acc[i] += a(r[i]);
                    ++ r[i];
                }
                if (acc[i] == b[i]) {
                    score += b[i];
                }
            }
        }
    };
    REP (y, n) {
        two_pointers([&](int x) { return a[y][x]; });
    }
    REP (x, n) {
        two_pointers([&](int y) { return a[y][x]; });
    }
    return score;
}

vector<vector<int> > solve(int n, array<int, 3> b, vector<vector<int> > l, vector<vector<int> > r) {
    vector<vector<int> > a = l;

    auto score_at_two_pointers = [&](int x, auto && a) {
        int score = 0;
        for (int b_i : b) {
            int acc = a(x);
            int l = x;
            while (l - 1 >= 0 and acc + a(l - 1) <= b_i) {
                acc += a(l - 1);
                -- l;
            }
            int r = x + 1;
            for (; l <= x; ++ l) {
                while (r < n and acc + a(r) <= b_i) {
                    acc += a(r);
                    ++ r;
                }
                if (acc == b_i) {
                    score += b_i;
                }
                acc -= a(l);
            }
        }
        return score;
    };
    auto score_at = [&](int y, int x) {
        int score = 0;
        score += score_at_two_pointers(x, [&](int x) { return a[y][x]; });
        score += score_at_two_pointers(y, [&](int y) { return a[y][x]; });
        return score;
    };

    int score = compute_score(n, b, a);
    int highscore = score;
    auto result = a;

    xor_shift_128 gen;
    constexpr int TIME_LIMIT = 3000;  // msec
    chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now();
    double temperature = 1;
    for (int iteration = 0; ; ++ iteration) {
        if (iteration % 1000 == 0) {
            chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now();
            temperature = 1 - chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() / (TIME_LIMIT * 0.9);
            if (temperature < 0) {
                cerr << "[*] iteration = " << iteration << ": done" << endl;
                break;
            }
        }

        int y, x;
        do {
            y = uniform_int_distribution<int>(0, n - 1)(gen);
            x = uniform_int_distribution<int>(0, n - 1)(gen);
        } while (r[y][x] - l[y][x] == 1);

        int delta;
        function<void ()> apply;

        if (bernoulli_distribution(0.5)(gen)) {
            int ny = y;
            int nx = x;
            if (bernoulli_distribution(0.5)(gen)) {
                ny = (y + 1 < n ? y + 1 : y - 1);
            } else {
                nx = (x + 1 < n ? x + 1 : x - 1);
            }
            if (not (l[ny][nx] <= a[y][x] and a[y][x] < r[ny][nx])) continue;
            if (not (l[y][x] <= a[ny][nx] and a[ny][nx] < r[y][x])) continue;
            int c1 = a[y][x];
            int c2 = a[ny][nx];
            delta = 0;
            delta -= score_at(y, x);
            a[y][x] = 100;  // infty
            delta -= score_at(ny, nx);
            a[ny][nx] = c1;
            delta += score_at(ny, nx);
            a[y][x] = c2;
            delta += score_at(y, x);
            a[y][x] = c1;
            a[ny][nx] = c2;
            apply = [&, ny, nx]() {  // ny, nx are captured by copy
// cerr << "swap " << y << ", " << x << " and " << ny << ", " << x << " with delta = " << delta << endl;
                swap(a[y][x], a[ny][nx]);
            };

        } else {
            array<int, 10> val;
            fill(ALL(val), -1);
            REP3 (c, l[y][x], r[y][x]) {
                int preserved = exchange(a[y][x], c);
                val[c] = score_at(y, x);
                swap(a[y][x], preserved);
            }
            int max_val = *max_element(ALL(val));
            int c;
            if (val[a[y][x]] < max_val) {
                do {
                    c = uniform_int_distribution<int>(l[y][x], r[y][x] - 1)(gen);
                } while (val[c] != max_val);
            } else {
                do {
                    c = uniform_int_distribution<int>(l[y][x], r[y][x] - 1)(gen);
                } while (c == a[y][x]);
            }
            delta = val[c] - val[a[y][x]];
            apply = [&, c]() {  // c is captured by copy
// cerr << "set " << y << ", " << x << " to " << c << " with delta = " << delta << endl;
                a[y][x] = c;
            };
        }

        auto probability = [&]() {
            constexpr double boltzmann = 0.03;
            return exp(boltzmann * delta) * temperature;
            // constexpr double boltzmann = 0.05;
            // return exp(boltzmann * delta / temperature);
        };
        if (0 <= delta or bernoulli_distribution(probability())(gen)) {
            if (delta < 0) {
                // cerr << "[*] iteration = " << iteration << ": forced with probability = " << probability() << endl;
            }
            apply();
            score += delta;
// assert (score == compute_score(n, b, a));
            if (highscore < score) {
                highscore = score;
                result = a;
                // cerr << "[*] iteration = " << iteration << ": highscore = " << highscore << endl;
            }
        }
    }

    assert (highscore == compute_score(n, b, result));
    cerr << "[*] score = " << highscore << endl;
    return result;
}

int main() {
    int n; cin >> n;
    array<int, 3> b; cin >> b[0] >> b[1] >> b[2];
    vector<vector<int> > l = make_table(n, n, int());
    vector<vector<int> > r = make_table(n, n, int());
    REP (y, n) REP (x, n) {
        cin >> l[y][x];
    }
    REP (y, n) REP (x, n) {
        cin >> r[y][x];
        ++ r[y][x];
    }
    auto a = solve(n, b, l, r);
    REP (y, n) REP (x, n) {
        assert (l[y][x] <= a[y][x] and a[y][x] < r[y][x]);
    }
    REP (y, n) {
        cout << a[y] << endl;
    }
    return 0;
}

提出情報

ジャッジ結果