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

• 問題: No.5022 XOR Printer
• ユーザー: bolero
• 提出日時: 2025-07-28 00:32:47
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,992 ms / 2,000 ms
• コード長: 22,492 bytes
• コンパイル時間: 4,906 ms
• コンパイル使用メモリ: 334,856 KB
• 実行使用メモリ: 7,720 KB
• スコア: 5,193,203,122
• 最終ジャッジ日時: 2025-07-28 00:34:36
• 合計ジャッジ時間: 108,385 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
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;

namespace approx_tsp
{
    // ---------------------
    // 距離関数オブジェクト
    // ---------------------
    struct Euclidean
    {
        using CostType = double;
        template <typename T, size_t D>
        double operator()(const array<T, D> &a, const array<T, D> &b) const
        {
            CostType sum = 0;
            for (size_t i = 0; i < D; i++)
            {
                CostType d = a[i] - b[i];
                sum += d * d;
            }
            return sqrt(sum);
        }
    };

    struct Manhattan
    {
        using CostType = int;
        template <typename T, size_t D>
        CostType operator()(const array<T, D> &a, const array<T, D> &b) const
        {
            CostType sum = 0;
            for (size_t i = 0; i < D; i++)
            {
                sum += abs(a[i] - b[i]);
            }
            return sum;
        }
    };

    // ---------------------
    // パスモード列挙型
    // ---------------------
    enum class PathMode
    {
        Closed, // 1周する必要がある 1 → 2　→ ...　→ N　→ 1
        Open    // 1周する必要がない 1 → 2　→ ...　→ N
    };

    // 参考 https://future-architect.github.io/articles/20211201a/
    template <
        typename Distance = Euclidean,
        PathMode Mode = PathMode::Closed>
    class ApproxTspSolver
    {
        using CostType = Distance::CostType;
        Distance dist;

        vector<vector<pair<CostType, int>>> cost_table;

        CostType double_bridge(vector<int> &nexts, vector<int> &prevs, const vector<vector<CostType>> &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;
            }

            shuffle_vector(random_ids);

            unordered_set<int> used;
            array<array<int, 2>, 4> bridge_edges;

            int bridge_cnt = 0;
            // ダブルブリッジするidを8つ選ぶ。 これは隣接する2項を4つ選ぶ。
            for (auto curr : random_ids)
            {
                int next = nexts[curr];

                if (used.contains(curr) || used.contains(next))
                {
                    continue;
                }

                used.insert(curr), used.insert(next);

                bridge_edges[bridge_cnt++] = {curr, next};
                if (bridge_cnt == 4)
                {
                    break;
                }
            }

            if (bridge_cnt != 4)
            {
                return 0;
            }

            vector<int> order(N);
            int now = 0;
            for (int i = 0; i < N; i++)
            {
                order[now] = i;
                now = nexts[now];
            }

            sort(bridge_edges.begin(), bridge_edges.end(), [&](const array<int, 2> &a, const array<int, 2> &b) -> bool
                 { return order[a[0]] < order[b[0]]; });

            CostType diff_cost = 0;
            for (int i = 0; i < 4; i++)
            {
                diff_cost -= costs[bridge_edges[i][0]][bridge_edges[i][1]];
            }

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

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

            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];
        }

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

            CostType 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:
        template <typename PointType, size_t D>
        pair<CostType, vector<int>> solve(const vector<array<PointType, D>> &points)
        {
            const int N = points.size();
            const int M = (Mode == PathMode::Closed ? N : N + 1);

            vector costs(M, vector<CostType>(M));

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (i == j)
                    {
                        continue;
                    }

                    costs[i][j] = dist(points[i], points[j]);
                }
            }

            return solve(costs);
        }

        pair<CostType, vector<int>> solve(const vector<vector<CostType>> &costs)
        {
            int N = costs.size();

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

            cost_table = vector(N, vector<pair<CostType, 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;

                CostType 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() != N - 1)
            {
                result_path.push_back(global_nexts[result_path.back()]);
            }

            if constexpr (Mode == PathMode::Open)
            {
                result_path.pop_back();
            }

            CostType result_cost = 0;
            for (int i = 0; i < result_path.size() - 1; i++)
            {
                result_cost += costs[result_path[i]][result_path[i + 1]];
            }

            if constexpr (Mode == PathMode::Closed)
            {
                result_cost += costs[result_path.back()][result_path.front()];
            }

            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(const array<int, 2> &from, const 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 rest_turn, 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;

    vector<string> first_query = gen_move_ans(now_pos, *(bit_mask_pos.begin()));
    first_query.push_back("C");
    now_s ^= A[bit_mask_pos.begin()->at(0)][bit_mask_pos.begin()->at(1)];
    first_query.push_back("W");
    A[bit_mask_pos.begin()->at(0)][bit_mask_pos.begin()->at(1)] ^= now_s;
    now_pos = *(bit_mask_pos.begin());
    bit_mask_pos.erase(bit_mask_pos.begin());

    result.insert(result.end(), first_query.begin(), first_query.end());

    // まずはbit maskを作っていく。
    approx_tsp::ApproxTspSolver<approx_tsp::Manhattan, approx_tsp::PathMode::Closed> tsp_solver;

    vector<vector<int>> costs(bit_mask_pos.size() + 1, vector<int>(bit_mask_pos.size() + 1, 0));
    rep(from, bit_mask_pos.size()) rep(to, bit_mask_pos.size())
    {
        costs[from][to] = abs(bit_mask_pos[from][0] - bit_mask_pos[to][0]) + abs(bit_mask_pos[from][1] - bit_mask_pos[to][1]);
    }

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

    auto [result_dist, result_root] = tsp_solver.solve(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});
        }
    }

    costs = vector<vector<int>>(pos_to_stamp.size() + 1, vector<int>(pos_to_stamp.size() + 1, 0));
    rep(from, pos_to_stamp.size()) rep(to, pos_to_stamp.size())
    {
        costs[from][to] = abs(pos_to_stamp[from][0] - pos_to_stamp[to][0]) + abs(pos_to_stamp[from][1] - pos_to_stamp[to][1]);
    }

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

    tie(result_dist, result_root) = tsp_solver.solve(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;
    }

    // 最後にswapする。
    rest_turn -= result.size();
    rest_turn -= 3;

    array<int, 2> finish_pos;
    int min_score = INT32_MAX;
    rep(i, N) rep(j, N)
    {
        if (abs(now_pos[0] - i) + abs(now_pos[1] - i) <= rest_turn)
        {
            if (A[i][j] < min_score)
            {
                finish_pos = array<int, 2>{(int)i, (int)j};
                min_score = A[i][j];
            }
        }
    }

    if (min_score != INT32_MAX)
    {
        vector<string> sub_query = gen_move_ans(now_pos, finish_pos);
        result.insert(result.end(), sub_query.begin(), sub_query.end());
        result.push_back("W");
        result.push_back("C");
        result.push_back("W");
        now_pos = finish_pos;
        swap(A[finish_pos[0]][finish_pos[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};
    vector<string> finish_query;
    int finish_score = 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});
            }
        }

        approx_tsp::ApproxTspSolver<approx_tsp::Manhattan, approx_tsp::PathMode::Closed> tsp_solver;
        vector<array<int, 2>> points = need_mask_pos;
        points.push_back(mask_pos);

        auto [sum_dist, result_root] = tsp_solver.solve(points);
        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 [temp_finish_score, temp_finish_query] = gen_finish_ans(T - ans.size() - query.size(), s, now_pos, bit_mask_pos, A);

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

        finish_score = temp_finish_score;
        swap(finish_query, temp_finish_query);
        ans.insert(ans.end(), query.begin(), query.end());
    }

    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(1975);

    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;
}