提出 886a0d8f-86ab-41e8-acab-e9afa522df3d

コード

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;

typedef array<int, 2> xy;

struct Op
{
    int id, H, W, a, b;
};

struct ApplyOp
{
    int op_idx, x, y;
};

struct State
{
    vector<vector<int>> A;
    vector<ApplyOp> applied_ops;
    int score;
    array<char, 3000> used;
};

int calc_score(const vector<vector<int>> &A, const vector<vector<int>> &B)
{
    int score = 0;
    int N = A.size();
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int diff = (int)A[i][j] - (int)B[i][j];
            score += diff * diff;
        }
    }
    return score;
}

int N, T;

void solve1()
{
    vector<vector<int>> init_A(N, vector<int>(N)), B(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> init_A[i][j];
    auto atmp = init_A;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> B[i][j];
    vector<Op> ops(T);
    for (int t = 0; t < T; ++t)
    {
        ops[t].id = t;
        cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
    }
    const int LIMIT = 100000;

    clock_t clk = clock();
    struct XORShiftRandom
    {
        uint64_t x = clock();
        inline uint64_t operator()()
        {
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            return x;
        }
        using result_type = uint64_t;
        constexpr static result_type min() { return 0; }
        constexpr static result_type max() { return UINT64_MAX; }
    } rng;

    constexpr int BEAM_WIDTH = 5;

    vector<State> states(1);
    states[0].A = init_A;
    states[0].score = calc_score(init_A, B);
    states[0].used.fill(0);

    array<vector<int>, 50> val_to_op;
    for (int i = 0; i < T; ++i)
    {
        val_to_op[ops[i].a].push_back(i);
    }

    while ((double)(clock() - clk) / CLOCKS_PER_SEC < 2.8)
    {
        vector<State> tmp_states = states;
        for (auto &[A, applied_ops, score, used] : states)
        {
            array<int, 50> candidates;
            candidates.fill(0);
            for (int i = 0; i < N; ++i)
            {
                for (int j = 0; j < N; ++j)
                {
                    int diff = (int)A[i][j] - (int)B[i][j];
                    candidates[A[i][j]] += diff * diff;
                }
            }
            for (int i = 0; i < 49; i++)
                candidates[i + 1] += candidates[i];
            int val = rng() % candidates.back();
            int tar;
            for (tar = 0; tar < 50; tar++)
            {
                if (candidates[tar] >= val)
                    break;
            }
            int id = val_to_op[tar][rng() % val_to_op[tar].size()], H = ops[id].H, W = ops[id].W, a = ops[id].a, b = ops[id].b;
            int uses = 0;
            if (used[id] < 3)
            {
                vector<vector<int>> pref(N + 1, vector<int>(N + 1, 0));
                bool anyPossible = false;
                for (int i = 0; i < N; ++i)
                {
                    int rowSum = 0;
                    for (int j = 0; j < N; ++j)
                    {
                        int w = 0;
                        if (A[i][j] == a)
                        {
                            int before = (int)a - (int)B[i][j];
                            int after = (int)b - (int)B[i][j];
                            w = after * after - before * before;
                            anyPossible = true;
                        }
                        rowSum += w;
                        pref[i + 1][j + 1] = pref[i][j + 1] + rowSum;
                    }
                }
                if (!anyPossible)
                    continue;
                int bestDelta = 0;
                int bestX = -1, bestY = -1;
                for (int x = 0; x + H <= N; ++x)
                {
                    for (int y = 0; y + W <= N; ++y)
                    {
                        int x2 = x + H, y2 = y + W;
                        int s = pref[x2][y2] - pref[x][y2] - pref[x2][y] + pref[x][y];
                        if (s < bestDelta)
                        {
                            bestDelta = s;
                            bestX = x;
                            bestY = y;
                        }
                    }
                }
                if (bestX == -1)
                    continue;
                for (int i = bestX; i < bestX + H; ++i)
                {
                    for (int j = bestY; j < bestY + W; ++j)
                    {
                        if (A[i][j] == a)
                            A[i][j] = b;
                    }
                }
                applied_ops.push_back(ApplyOp{id, bestX, bestY});
                ++used[id];
                score += bestDelta;
                tmp_states.push_back(State(A, applied_ops, score, used));
            }
        }
        swap(tmp_states, states);
        sort(states.begin(), states.end(), [](const State &s1, const State &s2)
             { return s1.score < s2.score; });
        if (states.size() > BEAM_WIDTH)
            states.resize(BEAM_WIDTH);
    }

    auto &best_state = states[0];

    cout << best_state.applied_ops.size() << "\n";

    for (auto &[op_idx, x, y] : best_state.applied_ops)
    {
        cout << op_idx << " " << x << " " << y << "\n";
    }
}

void solve2()
{
    vector<vector<int>> init_A(N, vector<int>(N)), B(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> init_A[i][j];
    auto atmp = init_A;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> B[i][j];
    vector<Op> ops(T);
    for (int t = 0; t < T; ++t)
    {
        ops[t].id = t;
        cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
    }
    const int LIMIT = 100000;

    clock_t clk = clock();
    struct XORShiftRandom
    {
        uint64_t x = 88172645463325252ULL;
        inline uint64_t operator()()
        {
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            return x;
        }
        using result_type = uint64_t;
        constexpr static result_type min() { return 0; }
        constexpr static result_type max() { return UINT64_MAX; }
    } rng;

    constexpr int BEAM_WIDTH = 22;

    vector<State> states(1);
    states[0].A = init_A;
    states[0].score = calc_score(init_A, B);
    states[0].used.fill(0);

    while ((double)(clock() - clk) / CLOCKS_PER_SEC < 2.8)
    {
        vector<State> tmp_states = states;
        for (auto &[A, applied_ops, score, used] : states)
        {
            int id = rng() % T, H = ops[id].H, W = ops[id].W, a = ops[id].a, b = ops[id].b;
            int uses = 0;
            if (used[id] < 3)
            {
                vector<vector<int>> pref(N + 1, vector<int>(N + 1, 0));
                bool anyPossible = false;
                for (int i = 0; i < N; ++i)
                {
                    int rowSum = 0;
                    for (int j = 0; j < N; ++j)
                    {
                        int w = 0;
                        if (A[i][j] == a)
                        {
                            int before = (int)A[i][j] - (int)B[i][j];
                            int after = (int)b - (int)B[i][j];
                            w = after * after - before * before;
                            anyPossible = true;
                        }
                        rowSum += w;
                        pref[i + 1][j + 1] = pref[i][j + 1] + rowSum;
                    }
                }
                if (!anyPossible)
                    continue;
                int bestDelta = 0;
                int bestX = -1, bestY = -1;
                for (int x = 0; x + H <= N; ++x)
                {
                    for (int y = 0; y + W <= N; ++y)
                    {
                        int x2 = x + H, y2 = y + W;
                        int s = pref[x2][y2] - pref[x][y2] - pref[x2][y] + pref[x][y];
                        if (s < bestDelta)
                        {
                            bestDelta = s;
                            bestX = x;
                            bestY = y;
                        }
                    }
                }
                if (bestX == -1)
                    continue;
                for (int i = bestX; i < bestX + H; ++i)
                {
                    for (int j = bestY; j < bestY + W; ++j)
                    {
                        if (A[i][j] == a)
                            A[i][j] = b;
                    }
                }
                applied_ops.push_back(ApplyOp{id, bestX, bestY});
                ++used[id];
                score += bestDelta;
                tmp_states.push_back(State(A, applied_ops, score, used));
            }
        }
        swap(tmp_states, states);
        sort(states.begin(), states.end(), [](const State &s1, const State &s2)
             { return s1.score < s2.score; });
        if (states.size() > BEAM_WIDTH)
            states.resize(BEAM_WIDTH);
    }

    auto &best_state = states[0];

    cout << best_state.applied_ops.size() << "\n";

    for (auto &[op_idx, x, y] : best_state.applied_ops)
    {
        cout << op_idx << " " << x << " " << y << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> T))
        return 0;
    // if (N <= 20)
    solve1();
    // else
    // solve2();
}
結果

問題	点数	言語	結果	実行時間	メモリ
A - Replace() は Replace() されました	182853497	C++	AC	2849 ms	4672 KiB