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

• 問題: No.5022 XOR Printer
• ユーザー: ぴぃいいいい
• 提出日時: 2025-07-28 08:00:45
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,804 ms / 2,000 ms
• コード長: 9,815 bytes
• コンパイル時間: 2,778 ms
• コンパイル使用メモリ: 214,356 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,456,616,252
• 最終ジャッジ日時: 2025-07-28 08:02:24
• 合計ジャッジ時間: 97,283 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <climits>
using namespace std;

int N, T;
vector<vector<int>> A;
vector<pair<int, int>> circuit; // 10x10のマス巡回回路
mt19937 rng;

// 各マスの各周回での行動を表す構造体
struct CellAction {
    bool copy;  
    bool write; 
};

// 解を表す構造体（複数周回分の行動を記録）
struct Solution {
    vector<vector<CellAction>> actions; // actions[round][cell_index]
    int max_rounds; // 最大周回数
    long long score;
    
    Solution(int rounds = 10) : max_rounds(rounds) {
        score = 0;
        actions.resize(max_rounds);
        for (int r = 0; r < max_rounds; r++) {
            actions[r].resize(N * N);
        }
    }
};

void input() {
    cin >> N >> T;
    A.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
}

// 10x10グリッドの巡回回路を生成（効率的なルート）
void generateCircuit() {
    circuit.clear();
    
    // 蛇行パターンで全マスを1回ずつ通る
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            // 偶数行：左から右へ
            for (int j = 0; j < N; j++) {
                circuit.push_back({i, j});
            }
        } else {
            // 奇数行：右から左へ
            for (int j = N - 1; j >= 0; j--) {
                circuit.push_back({i, j});
            }
        }
    }
}

// 移動コストを計算
int calculateMoveCost() {
    int moves = 0;
    for (int i = 1; i < circuit.size(); i++) {
        moves += abs(circuit[i].first - circuit[i-1].first) + 
                abs(circuit[i].second - circuit[i-1].second);
    }
    return moves;
}

// 解のスコアを計算（シミュレーション）
long long calculateScore(const Solution& sol) {
    vector<vector<int>> grid = A;
    int s = 0;
    int operations = 0;
    int currentR = 0, currentC = 0;
    
    // 複数周回のシミュレーション
    for (int round = 0; round < sol.max_rounds && operations < T; round++) {
        for (int cell_idx = 0; cell_idx < circuit.size() && operations < T; cell_idx++) {
            int targetR = circuit[cell_idx].first;
            int targetC = circuit[cell_idx].second;
            
            // 目標位置への移動
            while ((currentR != targetR || currentC != targetC) && operations < T) {
                if (currentR < targetR) {
                    operations++;
                    currentR++;
                } else if (currentR > targetR) {
                    operations++;
                    currentR--;
                } else if (currentC < targetC) {
                    operations++;
                    currentC++;
                } else if (currentC > targetC) {
                    operations++;
                    currentC--;
                } else {
                    break;
                }
            }
            
            if (operations >= T) break;
            
            // このマスでのコピー操作
            if (sol.actions[round][cell_idx].copy && operations < T) {
                operations++;
                s ^= grid[currentR][currentC];
            }
            
            // このマスでの書き込み操作
            if (sol.actions[round][cell_idx].write && operations < T) {
                operations++;
                grid[currentR][currentC] ^= s;
            }
        }
    }
    
    // 最終スコア計算
    long long totalScore = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            totalScore += grid[i][j];
        }
    }
    
    return totalScore;
}

// 初期解を生成
Solution generateRandomSolution() {
    Solution sol(8); // 最大8周回
    uniform_real_distribution<double> dist(0.0, 1.0);
    
    for (int round = 0; round < sol.max_rounds; round++) {
        for (int cell = 0; cell < N * N; cell++) {
            // 周回が進むにつれて操作確率を調整
            double copy_prob = 0.5 / (1.0 + round * 0.1);  // 周回が進むと確率減少
            double write_prob = 0.4 / (1.0 + round * 0.1);
            
            sol.actions[round][cell].copy = (dist(rng) < copy_prob);
            sol.actions[round][cell].write = (dist(rng) < write_prob);
        }
    }
    
    sol.score = calculateScore(sol);
    return sol;
}

// 近傍解を生成（特定の周回・セルの行動を変更）
Solution generateNeighbor(const Solution& current) {
    Solution neighbor = current;
    
    uniform_int_distribution<int> round_dist(0, current.max_rounds - 1);
    uniform_int_distribution<int> cell_dist(0, N * N - 1);
    uniform_real_distribution<double> action_dist(0.0, 1.0);
    
    // 変更する周回数を決定（1-3周回を変更）
    int rounds_to_change = uniform_int_distribution<int>(1, 3)(rng);
    
    for (int i = 0; i < rounds_to_change; i++) {
        int round = round_dist(rng);
        int cell = cell_dist(rng);
        
        // コピーまたは書き込み操作を反転
        if (action_dist(rng) < 0.5) {
            neighbor.actions[round][cell].copy = !neighbor.actions[round][cell].copy;
        } else {
            neighbor.actions[round][cell].write = !neighbor.actions[round][cell].write;
        }
    }
    
    neighbor.score = calculateScore(neighbor);
    return neighbor;
}

// 改良された焼きなまし法
Solution simulatedAnnealing() {
    const double TIME_LIMIT = 1.8;
    const double START_TEMP = 100000.0;
    const double END_TEMP = 0.1;
    
    auto start_time = chrono::high_resolution_clock::now();
    
    Solution current = generateRandomSolution();
    Solution best = current;
    
    uniform_real_distribution<double> prob_dist(0.0, 1.0);
    
    int iter = 0;
    int accepted = 0;
    int total_attempts = 0;
    int improvements = 0;
    
    while (true) {
        auto current_time = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(current_time - start_time).count();
        
        if (elapsed >= TIME_LIMIT) break;
        
        double progress = elapsed / TIME_LIMIT;
        
        // 温度スケジューリング
        double temp = START_TEMP * pow(END_TEMP / START_TEMP, progress);
        
        Solution neighbor = generateNeighbor(current);
        total_attempts++;
        
        double delta = neighbor.score - current.score;
        
        bool accept = false;
        if (delta > 0) {
            accept = true;
            improvements++;
        } else if (temp > END_TEMP) {
            double acceptance_prob = exp(delta / temp);
            accept = (acceptance_prob > prob_dist(rng));
        }
        
        if (accept) {
            current = neighbor;
            accepted++;
            
            if (current.score > best.score) {
                best = current;
            }
        }
        
        // デバッグ出力
        if (iter % 5000 == 0) {
            double acceptance_rate = (double)accepted / max(1, total_attempts);
            cerr << "Time: " << elapsed << "s, Temp: " << temp 
                 << ", Acceptance: " << acceptance_rate 
                 << ", Score: " << current.score << ", Best: " << best.score << endl;
        }
        
        iter++;
    }
    
    cerr << "Final: " << iter << " iterations, Best score: " << best.score << endl;
    return best;
}

// 操作列を生成
vector<char> generateOperations(const Solution& sol) {
    vector<char> operations;
    int currentR = 0, currentC = 0;
    
    // 複数周回の操作を生成
    for (int round = 0; round < sol.max_rounds && operations.size() < T; round++) {
        for (int cell_idx = 0; cell_idx < circuit.size() && operations.size() < T; cell_idx++) {
            int targetR = circuit[cell_idx].first;
            int targetC = circuit[cell_idx].second;
            
            // 移動操作
            while ((currentR != targetR || currentC != targetC) && operations.size() < T) {
                if (currentR < targetR) {
                    operations.push_back('D');
                    currentR++;
                } else if (currentR > targetR) {
                    operations.push_back('U');
                    currentR--;
                } else if (currentC < targetC) {
                    operations.push_back('R');
                    currentC++;
                } else if (currentC > targetC) {
                    operations.push_back('L');
                    currentC--;
                } else {
                    break;
                }
            }
            
            if (operations.size() >= T) break;
            
            // コピー操作
            if (sol.actions[round][cell_idx].copy && operations.size() < T) {
                operations.push_back('C');
            }
            
            // 書き込み操作
            if (sol.actions[round][cell_idx].write && operations.size() < T) {
                operations.push_back('W');
            }
        }
    }
    
    return operations;
}

int main() {
    auto start_time = chrono::high_resolution_clock::now();
    rng.seed(chrono::duration_cast<chrono::nanoseconds>(start_time.time_since_epoch()).count());
    
    input();
    generateCircuit();
    
    // 移動コストを確認
    int move_cost = calculateMoveCost();
    cerr << "Move cost per round: " << move_cost << endl;
    cerr << "Max possible rounds: " << T / move_cost << endl;
    
    Solution bestSolution = simulatedAnnealing();
    vector<char> operations = generateOperations(bestSolution);
    
    for (char op : operations) {
        cout << op << endl;
    }
    
    return 0;
}