#1108111 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: Khun
• 提出日時: 2025-07-26 16:57:32
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,205 ms / 2,000 ms
• コード長: 8,599 bytes
• コンパイル時間: 2,478 ms
• コンパイル使用メモリ: 211,172 KB
• 実行使用メモリ: 7,716 KB
• スコア: 5,199,478,785
• 最終ジャッジ日時: 2025-07-26 17:01:25
• 合計ジャッジ時間: 65,014 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;

class TimeKeeper {
public:
    // コンストラクタ：limitMillis に制限時間（ミリ秒）を指定
    TimeKeeper(long long limitMillis)
        : limitTime(limitMillis), startTime(std::chrono::steady_clock::now())
    {
    }

    // インスタンス生成直後は経過時間は0ミリ秒とみなす

    // 現在の経過時間（ミリ秒）を返す
    long long getNowTime() const {
        auto now = std::chrono::steady_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - startTime);
        return elapsed.count();
    }

    // 制限時間を超えているかを返す
    bool isTimeOver() const {
        return getNowTime() >= limitTime.count();
    }

private:
    std::chrono::steady_clock::time_point startTime;     // 開始時間
    std::chrono::milliseconds limitTime;                 // 制限時間（ミリ秒）
};

// 制限時間
int time_threshold = 1950;

// 変数
int n = 10, t = 1000;
vector<vector<int>> mass(n, vector<int>(n));
string ans;
int pos = 0;
int s = 0;

// ---- 追加: 焼きなまし法用の乱数生成器 ----
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 関数
void handle_input() {
    cin >> n >> t;
    rep(i, 0, n) rep(j, 0, n) cin >> mass[i][j];
}

string move(int from, int to) {
    int from_i = from / n;
    int from_j = from % n;
    int to_i = to / n;
    int to_j = to % n;

    string res;
    if(from_i < to_i) rep(i, 0, to_i-from_i) res.push_back('D');
    if(from_i > to_i) rep(i, 0, from_i-to_i) res.push_back('U');
    if(from_j < to_j) rep(i, 0, to_j-from_j) res.push_back('R');
    if(from_j > to_j) rep(i, 0, from_j-to_j) res.push_back('L');

    // cerrの出力はデバッグに役立つので残しておきます
    // cerr << from_i << " " << from_j << " " << to_i << " " << to_j << endl;
    // cerr << res << endl;

    return res;
}

// ---- 追加: 経路コスト計算用のヘルパー関数 ----
long long calculate_path_cost(int start_pos, const vector<int>& path, int end_pos, int grid_n) {
    long long cost = 0;
    int current_pos = start_pos;
    auto dist = [&](int p1, int p2) {
        if (p1 == -1 || p2 == -1) return 0LL;
        return (long long)abs(p1/grid_n - p2/grid_n) + abs(p1%grid_n - p2%grid_n);
    };

    if (path.empty()) {
        return dist(start_pos, end_pos);
    }

    cost += dist(current_pos, path[0]);
    current_pos = path[0];

    for (size_t i = 1; i < path.size(); ++i) {
        cost += dist(current_pos, path[i]);
        current_pos = path[i];
    }
    cost += dist(current_pos, end_pos);
    return cost;
}

// ---- 変更: trial関数にTimeKeeperを渡し、焼きなましを組み込む ----
void trial(const TimeKeeper& time_keeper) {
    vector<int> used;
    rrep(bit, 19, 0) {
        if (time_keeper.isTimeOver() || ans.size() >= t) break;

        // 元のロジックはそのまま: 必要に応じて'C'でsのbitを立てる
        {
            int dist = 1001001001;
            int to = -1;
            rep(i, 0, n) rep(j, 0, n) {
                if(find(used.begin(), used.end(), i*n+j) == used.end() and ((mass[i][j]^s)>>bit) & 1 and dist > abs(i-pos/n) + abs(j-pos%n)) {
                    dist = abs(i-pos/n) + abs(j-pos%n);
                    to = i*n+j;
                }
            }
            if(to != -1) {
                ans.append(move(pos, to));
                pos = to;
                ans.append("C");
                s = s ^ mass[to/n][to%n];
                used.push_back(to);
            }
        }

        if (time_keeper.isTimeOver() || ans.size() >= t) break;
        
        // 元のロジックで訪問候補地を集める
        vector<int> all_dests;
        int c_node = -1; // 'C'操作を行う特別なノード
        {
            vector<int> temp_dests; // 元の順序を保持するため一時的に格納
            rep(j1, 0, 5) rep(i, 0, n) rep(j2, 0, 2) {
                int ni = (bit & 1) ? i : n-i-1;
                ni = (j1 % 2 == 0) ? ni : n-ni-1;
                int nj2 = (bit & 1) ? j2 : 1-j2;
                nj2 = (i%2==0) ? nj2 : 1-nj2;
                int nj1 = (bit&1) ? j1 : 5-j1-1;
                int nj = 2*nj1 + nj2;
                if(((mass[ni][nj]>>bit) & 1) == 0) {
                    temp_dests.push_back(ni*n + nj);
                }
            }
            
            int c_node_cand = -1;
            for(int node : temp_dests) {
                all_dests.push_back(node);
                if(find(used.begin(), used.end(), node) == used.end()) {
                    c_node_cand = node;
                }
            }
            if (c_node_cand != -1) c_node = c_node_cand;
        }

        if (all_dests.empty()) continue;
        if (c_node == -1) {
            c_node = all_dests.back();
        }
        
        vector<int> w_nodes; // W操作を行うノード
        for (int node : all_dests) {
            if (node != c_node) {
                w_nodes.push_back(node);
            }
        }

        // ---- ここから焼きなまし法による経路最適化 ----
        if (w_nodes.size() > 1) {
            shuffle(w_nodes.begin(), w_nodes.end(), rng); // 初期解
            
            long long current_cost = calculate_path_cost(pos, w_nodes, c_node, n);
            
            double start_temp = 1.0; // パラメータは問題やコストのスケールに応じて調整
            double end_temp = 0.1;
            int iter_limit = 5000000; // 時間と相談して調整

            for (int i = 0; i < iter_limit; ++i) {
                if (i % 128 == 0 && time_keeper.getNowTime() > time_threshold*(20-bit)/13) break;

                int idx1 = rng() % w_nodes.size();
                int idx2 = rng() % w_nodes.size();
                if (idx1 == idx2) continue;
                if (idx1 > idx2) swap(idx1, idx2);

                // 2-optによるコスト差分計算 (高速化)
                auto dist = [&](int p1, int p2) {
                    if (p1 == -1 || p2 == -1) return 0LL;
                    return (long long)abs(p1/n - p2/n) + abs(p1%n - p2%n);
                };
                
                int prev_node1 = (idx1 == 0) ? pos : w_nodes[idx1 - 1];
                int node1 = w_nodes[idx1];
                int node2 = w_nodes[idx2];
                int next_node2 = (idx2 == w_nodes.size() - 1) ? c_node : w_nodes[idx2 + 1];

                long long diff = dist(prev_node1, node2) + dist(node1, next_node2) - dist(prev_node1, node1) - dist(node2, next_node2);
                
                double temp = start_temp + (end_temp - start_temp) * (double)i / iter_limit;

                if (diff < 0 || (double)rng() / rng.max() < exp(-diff / temp)) {
                    reverse(w_nodes.begin() + idx1, w_nodes.begin() + idx2 + 1);
                    current_cost += diff;
                }
            }
        }
        // ---- 焼きなまし終了 ----

        // 最適化された経路でansを構築
        for(int to : w_nodes) {
            if (ans.size() >= t) break;
            ans.append(move(pos, to));
            pos = to;
            ans.append("W");
            mass[to/n][to%n] = s ^ mass[to/n][to%n];
        }
        if (ans.size() >= t) continue;

        if (c_node != -1) {
            ans.append(move(pos, c_node));
            pos = c_node;
            // 元のコードの特殊な条件を再現
            if(bit == 19) {
                ans.append("W");
                mass[pos/n][pos%n] = s ^ mass[pos/n][pos%n];
            } else {
                ans.append("C");
                s ^= mass[pos/n][pos%n];
                used.push_back(pos);
            }
        }
    }
}

void answer() {
    // 最終的な答えをT文字に切り詰めて出力
    string final_ans = ans.substr(0, min((size_t)t, ans.size()));
    // インタラクティブ問題で一般的な1文字ずつの改行付き出力
    for(char c : final_ans) {
        cout << c << endl;
    }
}

int main(void) {
    auto time_keeper = TimeKeeper(time_threshold);
    handle_input();
    
    trial(time_keeper); // TimeKeeperインスタンスを渡す
    
    answer();
}