#1107974 (C++23) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: bolero
• 提出日時: 2025-07-26 15:37:13
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,966 ms / 2,000 ms
• コード長: 18,386 bytes
• コンパイル時間: 4,827 ms
• コンパイル使用メモリ: 336,180 KB
• 実行使用メモリ: 7,720 KB
• スコア: 5,151,017,040
• 最終ジャッジ日時: 2025-07-26 15:39:01
• 合計ジャッジ時間: 107,137 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
other	AC * 50

ソースコード

/*#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")*/

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort(v.rbegin(), v.rend())
#define REVERSE(v) reverse(v.begin(), v.end())

template <typename T>
void printlnVector(const T &v)
{
    for (auto n : v)
    {
        cout << n << endl;
    }
}

template <typename T>
void printVector(const T &v, char suffix = '\n')
{
    for (auto n : v)
    {
        cout << n << " ";
    }
    cout << suffix;
}

class FastRandomEngine
{
public:
    using result_type = uint64_t;
    result_type state;

private:
    // 0以上MAX以下の整数をとる乱数 xorshift https://ja.wikipedia.org/wiki/Xorshift
    // 2step xorshift の方が計算が速いが質が悪いらしい？
    inline result_type randXor() noexcept
    {
        state ^= state << 7;
        state ^= state >> 9;

        return state;
    }

public:
    FastRandomEngine(result_type seed = 1) : state(seed)
    {
        assert(seed != 0);
    }

    inline result_type operator()() noexcept
    {
        return randXor();
    }

    static inline constexpr result_type min() noexcept
    {
        return numeric_limits<result_type>::min();
    }

    static inline constexpr result_type max() noexcept
    {
        return numeric_limits<result_type>::max();
    }

    inline constexpr double inv_max() noexcept
    {
        return 1.0 / max();
    }

    inline long long random_int(const pair<long long, long long> &min_max) noexcept
    {
        return random_int(min_max.first, min_max.second);
    }

    inline long long random_int(long long min, long long max) noexcept
    {
        long long width = max - min + 1;
        return randXor() % width + min;
    }

    inline double random_real(const pair<double, double> &min_max) noexcept
    {
        return random_real(min_max.first, min_max.second);
    }

    inline double random_real(double min, double max) noexcept
    {
        return rand01() * (max - min) + min;
    }

    // 0以上1未満の小数をとる乱数
    inline double rand01() noexcept
    {
        return randXor() * inv_max();
    }
};
FastRandomEngine rand_engine(1);

template <class T>
inline void shuffle_vector(vector<T> &v) noexcept
{
    shuffle(v.begin(), v.end(), rand_engine);
}

template <class T>
inline T random_select(const vector<T> &v) noexcept
{
    return v[rand_engine.random_int(0, v.size() - 1)];
}

inline double generate_normal(double mu, double sigma) noexcept
{
    normal_distribution<double> dist(mu, sigma);
    return dist(rand_engine);
};

class Timer
{
private:
    chrono::high_resolution_clock::time_point start_time_;
    int64_t now_process_time_;
    int64_t time_threshold_ = -1;

public:
    // 時間制限をミリ秒単位で指定してインスタンスをつくる。
    Timer() : start_time_(chrono::high_resolution_clock::now()), now_process_time_(0) {}

    // この関数を実行するとtimerの経過時間が更新される。
    // 時間取得処理にかかるわずかな時間を省略するためにこのようにしている。
    inline void update_process_time()
    {
        auto diff = chrono::high_resolution_clock::now() - this->start_time_;
        now_process_time_ = chrono::duration_cast<chrono::milliseconds>(diff).count();
    }

    inline void set_limit_time(const int64_t &time_threshold)
    {
        this->time_threshold_ = time_threshold;
    }

    inline int64_t get_process_time() const
    {
        return now_process_time_;
    }

    inline bool over_limit_time() const
    {
        return get_rest_time() < 0;
    }

    inline int64_t get_rest_time() const
    {
        return time_threshold_ - get_process_time();
    }

    inline int64_t get_limit_time() const
    {
        return time_threshold_;
    }
};

#include <bits/stdc++.h>
using namespace std;

// 参考 https://future-architect.github.io/articles/20211201a/
template <typename T>
class ApproxTspSolver
{
    vector<vector<pair<T, int>>> cost_table;

    T double_bridge(vector<int> &nexts, vector<int> &prevs, const vector<vector<T>> &costs)
    {
        int N = nexts.size();
        if (nexts.size() < 8)
        {
            return 0;
        }

        static vector<int> random_ids;
        if (random_ids.size() != nexts.size())
        {
            random_ids = nexts;
        }

        vector<int> x(nexts.size());
        for (int i = 0; i < nexts.size(); i++)
        {
            x[i] = nexts[x[i]];
        }

        unordered_set<int> used;
        vector<int> swaps;

        shuffle_vector(random_ids);

        for (auto random_id : random_ids)
        {
            if (used.contains(random_id) || used.contains((random_id + 1) % N))
            {
                continue;
            }

            used.insert(random_id);
            used.insert((random_id + 1) % N);

            swaps.push_back(random_id);
            if (swaps.size() == 4)
            {
                break;
            }
        }

        if (swaps.size() != 4)
        {
            return 0;
        }

        sort(swaps.begin(), swaps.end());

        vector<int> u(4), v(4);
        for (int i = 0; i < 4; i++)
        {
            u[i] = x[swaps[i]], v[i] = nexts[u[i]];
        }

        T diff_cost = 0;
        for (int i = 0; i < 4; i++)
        {
            diff_cost -= costs[u[i]][v[i]];
        }

        for (int i = 0; i < 4; i++)
        {
            nexts[u[i]] = v[(i + 2) % 4];
            prevs[v[(i + 2) % 4]] = u[i];
        }

        for (int i = 0; i < 4; i++)
        {
            diff_cost += costs[u[i]][v[(i + 2) % 4]];
        }

        return diff_cost;
    }

    // l ~ r までの向きを逆にする(lとrは含まない)
    void reverse_node(vector<int> &nexts, vector<int> &prevs, int l, int r)
    {
        nexts[r] = prevs[r];
        int now = nexts[r];
        while (now != l)
        {
            swap(nexts[now], prevs[now]);
            now = nexts[now];
        }
        prevs[l] = nexts[l];
    }

    T two_opt(vector<int> &nexts, vector<int> &prevs, const vector<vector<T>> &costs)
    {
        int N = nexts.size();
        if (nexts.size() < 4)
        {
            return 0;
        }

        T diff_cost = 0;

        auto try_swap = [&](int u1, int u2) -> bool
        {
            for (auto [cost, u3] : cost_table[u1])
            {
                int u4 = nexts[u3];
                if (u2 == u3)
                {
                    break;
                }
                if (costs[u1][u2] + costs[u3][u4] <= costs[u1][u3] + costs[u2][u4])
                {
                    continue;
                }

                diff_cost -= costs[u1][u2], diff_cost -= costs[u3][u4];
                diff_cost -= costs[u2][nexts[u2]], diff_cost -= costs[u3][prevs[u3]];

                reverse_node(nexts, prevs, u2, u3);
                nexts[u1] = u3, prevs[u3] = u1;
                nexts[u2] = u4, prevs[u4] = u2;

                diff_cost += costs[u1][u3], diff_cost += costs[u2][u4];
                diff_cost += costs[u3][nexts[u3]], diff_cost += costs[u2][prevs[u2]];

                return true;
            }

            for (auto [cost, u4] : cost_table[u2])
            {
                int u3 = prevs[u4];
                if (u1 == u4)
                {
                    break;
                }
                if (costs[u1][u2] + costs[u3][u4] <= costs[u1][u3] + costs[u2][u4])
                {
                    continue;
                }

                diff_cost -= costs[u1][u2], diff_cost -= costs[u3][u4];
                diff_cost -= costs[u2][nexts[u2]], diff_cost -= costs[u3][prevs[u3]];

                reverse_node(nexts, prevs, u2, u3);
                nexts[u1] = u3, prevs[u3] = u1;
                nexts[u2] = u4, prevs[u4] = u2;

                diff_cost += costs[u1][u3], diff_cost += costs[u2][u4];
                diff_cost += costs[u3][nexts[u3]], diff_cost += costs[u2][prevs[u2]];

                return true;
            }

            return false;
        };

        while (true)
        {
            bool update = false;
            for (int u1 = 0; u1 < N; u1++)
            {
                int u2 = nexts[u1];

                if (try_swap(u1, u2))
                {
                    update = true;
                    break;
                }
            }

            if (!update)
            {
                break;
            }
        }

        return diff_cost;
    }

public:
    pair<T, vector<int>> solve(const vector<int> &x, const vector<vector<T>> &costs)
    {
        int N = x.size();

        // i番目の前後の頂点が何番かを管理する
        vector<int> nexts(x.size()), prevs(x.size());
        for (int i = 0; i < x.size(); i++)
        {
            nexts[i] = (i + 1) % x.size();
            prevs[i] = (i - 1 + x.size()) % x.size();
        }

        cost_table = vector(N, vector<pair<T, int>>());
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (i == j)
                {
                    continue;
                }
                cost_table[i].push_back(pair(costs[i][j], j));
            }
            sort(cost_table[i].begin(), cost_table[i].end());
        }

        vector<int> global_nexts = nexts, global_prevs = prevs;
        for (int i = 0; i < 100; i++)
        {
            nexts = global_nexts, prevs = global_prevs;

            T diff_score = 0;
            diff_score += double_bridge(nexts, prevs, costs);
            diff_score += two_opt(nexts, prevs, costs);

            if (diff_score < 0)
            {
                global_nexts = nexts, global_prevs = prevs;
            }
        }

        vector<int> result_path = {global_nexts.back()};
        while (result_path.back() != (int)x.size() - 1)
        {
            result_path.push_back(global_nexts[result_path.back()]);
        }

        T result_cost = 0;
        for (int i = 0; i < N; i++)
        {
            result_cost += costs[result_path[i]][result_path[(i + 1) % N]];
        }

        return pair(result_cost, result_path);
    }
};

const int N = 10, T = 1000, max_bit = 19;

vector<array<int, 2>> find_has_start_with_str_pos(const string &str, const array<array<int, N>, N> &A)
{
    vector<array<int, 2>> pos;
    rep(h, N) rep(w, N)
    {
        if (bitset<20>(A[h][w]).to_string().starts_with(str))
        {
            pos.push_back(array<int, 2>{(int)h, (int)w});
        }
    }

    return pos;
}

vector<string> gen_move_ans(array<int, 2> &from, array<int, 2> &to)
{
    vector<string> res;
    // 縦方向の移動
    int dr = to[0] - from[0];
    if (dr > 0)
    {
        // 下方向に dr 回
        for (int i = 0; i < dr; i++)
            res.push_back("D");
    }
    else
    {
        // dr < 0 のときは上方向に -dr 回
        for (int i = 0; i < -dr; i++)
            res.push_back("U");
    }
    // 横方向の移動
    int dc = to[1] - from[1];
    if (dc > 0)
    {
        // 右方向に dc 回
        for (int i = 0; i < dc; i++)
            res.push_back("R");
    }
    else
    {
        // dc < 0 のときは左方向に -dc 回
        for (int i = 0; i < -dc; i++)
            res.push_back("L");
    }
    return res;
}

pair<int, vector<string>> gen_finish_ans(int now_s, array<int, 2> now_pos, vector<array<int, 2>> &bit_mask_pos, array<array<int, N>, N> A)
{
    int sum_score = 0;
    vector<string> result;

    // まずはbit maskを作っていく。
    ApproxTspSolver<double> tsp_solver;

    vector<int> root(bit_mask_pos.size() + 1);
    iota(root.begin(), root.end(), 0);
    vector<vector<double>> costs(root.size(), vector<double>(root.size(), 0));
    rep(from, bit_mask_pos.size()) rep(to, bit_mask_pos.size())
    {
        costs[from][to] = hypot(bit_mask_pos[from][0] - bit_mask_pos[to][0], bit_mask_pos[from][1] - bit_mask_pos[to][1]);
    }

    rep(i, bit_mask_pos.size())
    {
        costs[bit_mask_pos.size()][i] = hypot(bit_mask_pos[i][0] - now_pos[0], bit_mask_pos[i][1] - now_pos[1]);
        costs[i][bit_mask_pos.size()] = hypot(bit_mask_pos[i][0] - now_pos[0], bit_mask_pos[i][1] - now_pos[1]);
    }

    auto [result_dist, result_root] = tsp_solver.solve(root, costs);
    result_root.pop_back();

    for (auto root_i : result_root)
    {
        vector<string> sub_query = gen_move_ans(now_pos, bit_mask_pos[root_i]);
        result.insert(result.end(), sub_query.begin(), sub_query.end());
        result.push_back("C");
        now_pos = bit_mask_pos[root_i];
        now_s ^= A[bit_mask_pos[root_i][0]][bit_mask_pos[root_i][1]];
    }

    // sを必要な場所にスタンプしていって総和を高める。
    vector<array<int, 2>> pos_to_stamp;
    rep(h, N) rep(w, N)
    {
        if (A[h][w] < A[h][w] ^ now_s)
        {
            pos_to_stamp.push_back(array<int, 2>{(int)h, (int)w});
        }
    }

    root = vector<int>(pos_to_stamp.size() + 1);
    iota(root.begin(), root.end(), 0);
    costs = vector<vector<double>>(root.size(), vector<double>(root.size(), 0));
    rep(from, pos_to_stamp.size()) rep(to, pos_to_stamp.size())
    {
        costs[from][to] = hypot(pos_to_stamp[from][0] - pos_to_stamp[to][0], pos_to_stamp[from][1] - pos_to_stamp[to][1]);
    }

    rep(i, pos_to_stamp.size())
    {
        costs[pos_to_stamp.size()][i] = hypot(pos_to_stamp[i][0] - now_pos[0], pos_to_stamp[i][1] - now_pos[1]);
        costs[i][pos_to_stamp.size()] = hypot(pos_to_stamp[i][0] - now_pos[0], pos_to_stamp[i][1] - now_pos[1]);
    }

    tie(result_dist, result_root) = tsp_solver.solve(root, costs);
    result_root.pop_back();
    for (auto root_i : result_root)
    {
        vector<string> sub_query = gen_move_ans(now_pos, pos_to_stamp[root_i]);
        result.insert(result.end(), sub_query.begin(), sub_query.end());
        result.push_back("W");
        now_pos = pos_to_stamp[root_i];
        A[pos_to_stamp[root_i][0]][pos_to_stamp[root_i][1]] ^= now_s;
    }

    rep(i, N) rep(j, N)
    {
        sum_score += A[i][j];
    }

    return {sum_score, result};
}

pair<int, vector<string>> solve(array<array<int, N>, N> A, bool not_shuffle)
{
    vector<string> ans;

    int s = 0;
    vector<array<int, 2>> bit_mask_pos;
    array<int, 2> now_pos = {0, 0};
    for (int bit = 0; bit < 20; bit++)
    {
        int backup_s = s;
        array<int, 2> backup_now_pos = now_pos;
        array<array<int, N>, N> backup_A = A;
        string check_str = string(bit + 1, '0');
        check_str[bit] = '1';

        auto mask_positions = find_has_start_with_str_pos(check_str, A);

        if (mask_positions.size() == 0)
        {
            break;
        }

        auto mask_pos = not_shuffle ? mask_positions[0] : random_select(mask_positions);

        bit_mask_pos.push_back(mask_pos);

        vector<array<int, 2>> need_mask_pos;
        rep(h, N) rep(w, N)
        {
            if (mask_pos == array<int, 2>{(int)h, (int)w})
            {
                continue;
            }

            if ((A[h][w] >> (max_bit - bit)) & 1)
            {
                need_mask_pos.push_back({(int)h, (int)w});
            }
        }

        ApproxTspSolver<double> tsp_solver;
        vector<int> root(need_mask_pos.size() + 1);
        iota(root.begin(), root.end(), 0);
        vector<vector<double>> costs(root.size(), vector<double>(root.size(), 0));
        rep(from, need_mask_pos.size()) rep(to, need_mask_pos.size())
        {
            costs[from][to] = hypot(need_mask_pos[from][0] - need_mask_pos[to][0], need_mask_pos[from][1] - need_mask_pos[to][1]);
        }

        rep(i, need_mask_pos.size())
        {
            costs[need_mask_pos.size()][i] = hypot(need_mask_pos[i][0] - mask_pos[0], need_mask_pos[i][1] - mask_pos[1]);
            costs[i][need_mask_pos.size()] = hypot(need_mask_pos[i][0] - mask_pos[0], need_mask_pos[i][1] - mask_pos[1]);
        }

        auto [sum_dist, result_root] = tsp_solver.solve(root, costs);
        result_root.pop_back();

        vector<string> query = gen_move_ans(now_pos, mask_pos);
        query.push_back("C");
        s ^= A[mask_pos[0]][mask_pos[1]];
        now_pos = mask_pos;

        for (auto root_i : result_root)
        {
            vector<string> sub_query = gen_move_ans(now_pos, need_mask_pos[root_i]);
            query.insert(query.end(), sub_query.begin(), sub_query.end());
            query.push_back("W");
            now_pos = need_mask_pos[root_i];
            A[need_mask_pos[root_i][0]][need_mask_pos[root_i][1]] ^= s;
        }

        vector<string> sub_query = gen_move_ans(now_pos, mask_pos);
        query.insert(query.end(), sub_query.begin(), sub_query.end());
        query.push_back("C");
        s ^= A[mask_pos[0]][mask_pos[1]];
        now_pos = mask_pos;

        auto finish_query = gen_finish_ans(s, now_pos, bit_mask_pos, A).second;

        if (T < ans.size() + query.size() + finish_query.size())
        {
            s = backup_s;
            bit_mask_pos.pop_back();
            now_pos = backup_now_pos;
            A = backup_A;
            break;
        }

        ans.insert(ans.end(), query.begin(), query.end());
    }

    auto [finish_score, finish_query] = gen_finish_ans(s, now_pos, bit_mask_pos, A);
    ans.insert(ans.end(), finish_query.begin(), finish_query.end());

    cerr << "score = " << finish_score << endl;

    return {finish_score, ans};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Timer timer;
    timer.set_limit_time(1950);

    int in_N, in_T;
    cin >> in_N >> in_T;

    array<array<int, N>, N> A;
    rep(h, N) rep(w, N)
    {
        cin >> A[h][w];
    }

    int best_score = 0;
    vector<string> best_query;

    while (!timer.over_limit_time())
    {
        auto [score, query] = solve(A, best_score == 0);

        if (best_score < score)
        {
            best_score = score;
            swap(best_query, query);
        }

        timer.update_process_time();
    }

    cerr << endl;

    cerr << "best score = " << best_score << endl;

    printlnVector(best_query);

    return 0;
}