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

• 問題: No.5022 XOR Printer
• ユーザー: ぴぃいいいい
• 提出日時: 2025-07-28 19:39:33
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,804 ms / 2,000 ms
• コード長: 14,285 bytes
• コンパイル時間: 2,094 ms
• コンパイル使用メモリ: 203,256 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,605,841,118
• 最終ジャッジ日時: 2025-07-28 19:41:10
• 合計ジャッジ時間: 96,507 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

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

ソースコード

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

// ===== グローバル変数と定数 =====
int N, T;
vector<vector<int>> A;
mt19937 rng;

constexpr int MAX_ROUNDS = 6;
constexpr double TIME_LIMIT = 1.8;
constexpr double START_TEMP = 300000.0;
constexpr double END_TEMP = 0.001;

// ===== 最適化されたデータ構造 =====

// キャッシュ効率を考慮したアクション配列
struct alignas(16) FastAction {
    uint64_t copy_bits;   // 各周回のコピーフラグをビットパック
    uint64_t write_bits;  // 各周回の書き込みフラグをビットパック
    
    FastAction() : copy_bits(0), write_bits(0) {}
    
    inline bool getCopy(int round) const {
        return (copy_bits >> round) & 1;
    }
    
    inline bool getWrite(int round) const {
        return (write_bits >> round) & 1;
    }
    
    inline void setCopy(int round, bool value) {
        if (value) {
            copy_bits |= (1ULL << round);
        } else {
            copy_bits &= ~(1ULL << round);
        }
    }
    
    inline void setWrite(int round, bool value) {
        if (value) {
            write_bits |= (1ULL << round);
        } else {
            write_bits &= ~(1ULL << round);
        }
    }
    
    inline void flip(int round, bool is_copy) {
        if (is_copy) {
            copy_bits ^= (1ULL << round);
        } else {
            write_bits ^= (1ULL << round);
        }
    }
};

// 最適化されたソリューション
struct alignas(16) FastSolution {
    FastAction actions[100];  // 固定サイズ配列でキャッシュ効率向上
    long long score;
    
    FastSolution() : score(0) {}
    
    // 高速コピー
    inline void copyFrom(const FastSolution& other) {
        memcpy(actions, other.actions, sizeof(actions));
        score = other.score;
    }
};

// ===== 最適化されたゲームシミュレーター =====
class OptimizedGameSimulator {
private:
    alignas(16) int route_r[100];  // 行座標を事前計算
    alignas(16) int route_c[100];  // 列座標を事前計算
    alignas(16) int grid_flat[100]; // グリッドを1次元配列に平坦化
    
public:
    OptimizedGameSimulator() {
        // 蛇行ルートを事前計算して配列に格納
        int idx = 0;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < N; j++) {
                    route_r[idx] = i;
                    route_c[idx] = j;
                    idx++;
                }
            } else {
                for (int j = N - 1; j >= 0; j--) {
                    route_r[idx] = i;
                    route_c[idx] = j;
                    idx++;
                }
            }
        }
    }
    
    // 最適化されたスコア計算
    inline long long calculateScore(const FastSolution& sol) {
        // グリッドを1次元配列にコピー（キャッシュ効率向上）
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid_flat[i * N + j] = A[i][j];
            }
        }
        
        int s = 0;
        int operations = 0;
        int currentR = 0, currentC = 0;
        
        // 複数周回の処理（最適化版）
        for (int round = 0; round < MAX_ROUNDS && operations < T; round++) {
            for (int i = 0; i < 100 && operations < T; i++) {
                int targetR = route_r[i];
                int targetC = route_c[i];
                
                // マンハッタン距離による高速移動計算
                int move_ops = abs(currentR - targetR) + abs(currentC - targetC);
                operations += move_ops;
                currentR = targetR;
                currentC = targetC;
                
                if (operations >= T) break;
                
                int cell_idx = currentR * N + currentC;
                
                // コピー操作
                if (sol.actions[i].getCopy(round) && operations < T) {
                    operations++;
                    s ^= grid_flat[cell_idx];
                }
                
                // 書き込み操作
                if (sol.actions[i].getWrite(round) && operations < T) {
                    operations++;
                    grid_flat[cell_idx] ^= s;
                }
            }
        }
        
        // 高速合計計算（ループアンローリング）
        return calculateOptimizedSum();
    }
    
private:
    // ループアンローリングによる高速合計計算
    inline long long calculateOptimizedSum() {
        long long total = 0;
        
        // 4つずつまとめて処理（ループアンローリング）
        int i = 0;
        for (; i <= 96; i += 4) {
            total += grid_flat[i] + grid_flat[i+1] + grid_flat[i+2] + grid_flat[i+3];
        }
        
        // 残りの要素を処理
        for (; i < 100; i++) {
            total += grid_flat[i];
        }
        
        return total;
    }
};

// ===== 高速化された最適化器 =====
class TurboOptimizer {
private:
    OptimizedGameSimulator simulator;
    
    // 高速乱数生成器（xorshift）
    uint64_t xorshift_state;
    
    inline uint64_t xorshift64() {
        xorshift_state ^= xorshift_state << 13;
        xorshift_state ^= xorshift_state >> 7;
        xorshift_state ^= xorshift_state << 17;
        return xorshift_state;
    }
    
    inline double fastRandom() {
        return (xorshift64() & 0x7FFFFFFF) * (1.0 / 2147483648.0);
    }
    
    inline int fastRandomInt(int max_val) {
        return xorshift64() % max_val;
    }
    
public:
    TurboOptimizer() {
        xorshift_state = chrono::high_resolution_clock::now().time_since_epoch().count();
    }
    
    // 高速初期解生成
    FastSolution generateInitialSolution() {
        FastSolution sol;
        
        // 事前計算された確率テーブルを使用
        static const double copy_probs[MAX_ROUNDS] = {0.55, 0.44, 0.35, 0.28, 0.22, 0.18};
        static const double write_probs[MAX_ROUNDS] = {0.45, 0.36, 0.29, 0.23, 0.18, 0.15};
        
        for (int i = 0; i < 100; i++) {
            // 境界効果の事前計算
            int row = i / N;
            int col = i % N;
            double boundary_factor = (row == 0 || row == N-1 || col == 0 || col == N-1) ? 1.4 : 1.0;
            
            for (int round = 0; round < MAX_ROUNDS; round++) {
                double copy_threshold = copy_probs[round] * boundary_factor;
                double write_threshold = write_probs[round] * boundary_factor;
                
                sol.actions[i].setCopy(round, fastRandom() < copy_threshold);
                sol.actions[i].setWrite(round, fastRandom() < write_threshold);
            }
        }
        
        sol.score = simulator.calculateScore(sol);
        return sol;
    }
    
    // 超高速近傍生成
    inline FastSolution generateNeighbor(const FastSolution& current) {
        FastSolution neighbor;
        neighbor.copyFrom(current);
        
        // 適応的変更数（ビット操作で高速化）
        int change_count = 1 + (fastRandomInt(100) < 25) + (fastRandomInt(100) < 10);
        
        for (int k = 0; k < change_count; k++) {
            int cell = fastRandomInt(100);
            int round = fastRandomInt(MAX_ROUNDS);
            bool is_copy = fastRandomInt(2) == 0;
            
            neighbor.actions[cell].flip(round, is_copy);
        }
        
        neighbor.score = simulator.calculateScore(neighbor);
        return neighbor;
    }
    
    // ターボ焼きなまし法
    FastSolution optimize() {
        auto start_time = chrono::high_resolution_clock::now();
        
        FastSolution current = generateInitialSolution();
        FastSolution best = current;
        FastSolution global_best = current;
        
        int iter = 0;
        int accepted = 0;
        int improvements = 0;
        int restarts = 0;
        
        // 温度計算用の定数を事前計算
        const double log_temp_ratio = log(END_TEMP / START_TEMP);
        
        // 高速exp近似用のテーブル
        static bool exp_table_initialized = false;
        static double exp_table[10000];
        if (!exp_table_initialized) {
            for (int i = 0; i < 10000; i++) {
                exp_table[i] = exp(-i * 0.001);
            }
            exp_table_initialized = true;
        }
        
        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 * exp(log_temp_ratio * progress);
            
            FastSolution neighbor = generateNeighbor(current);
            double delta = neighbor.score - current.score;
            
            bool accept = false;
            if (delta > 0) {
                accept = true;
                improvements++;
            } else if (temp > END_TEMP) {
                // 高速exp近似（テーブル参照）
                double ratio = -delta / temp;
                if (ratio < 10.0) {
                    int table_idx = (int)(ratio * 1000);
                    if (table_idx < 10000) {
                        accept = (fastRandom() < exp_table[table_idx]);
                    }
                }
            }
            
            if (accept) {
                current.copyFrom(neighbor);
                accepted++;
                
                if (current.score > global_best.score) {
                    global_best.copyFrom(current);
                }
            }
            
            // 適応的再スタート
            if (iter % 100000 == 0 && progress > 0.1 && progress < 0.8) {
                if (improvements < iter / 2000) {
                    current = generateInitialSolution();
                    restarts++;
                }
            }
            
            // デバッグ出力の頻度を調整
            if (iter % 25000 == 0) {
                double acceptance_rate = (double)accepted / max(1, iter);
                cerr << "Time: " << elapsed << "s, Temp: " << temp 
                     << ", Accept: " << acceptance_rate 
                     << ", Score: " << current.score << ", Best: " << global_best.score 
                     << ", Restarts: " << restarts << endl;
            }
            
            iter++;
        }
        
        cerr << "Final: " << iter << " iterations, " << improvements << " improvements, "
             << restarts << " restarts, Best score: " << global_best.score << endl;
        
        return global_best;
    }
};

// ===== 高速操作列生成 =====
vector<char> generateFastOperations(const FastSolution& sol) {
    vector<char> operations;
    operations.reserve(T);  // メモリ再確保を防ぐ
    
    int currentR = 0, currentC = 0;
    
    // 事前計算されたルート
    static const pair<int, int> route[100] = {
        {0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{0,8},{0,9},
        {1,9},{1,8},{1,7},{1,6},{1,5},{1,4},{1,3},{1,2},{1,1},{1,0},
        {2,0},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},{2,7},{2,8},{2,9},
        {3,9},{3,8},{3,7},{3,6},{3,5},{3,4},{3,3},{3,2},{3,1},{3,0},
        {4,0},{4,1},{4,2},{4,3},{4,4},{4,5},{4,6},{4,7},{4,8},{4,9},
        {5,9},{5,8},{5,7},{5,6},{5,5},{5,4},{5,3},{5,2},{5,1},{5,0},
        {6,0},{6,1},{6,2},{6,3},{6,4},{6,5},{6,6},{6,7},{6,8},{6,9},
        {7,9},{7,8},{7,7},{7,6},{7,5},{7,4},{7,3},{7,2},{7,1},{7,0},
        {8,0},{8,1},{8,2},{8,3},{8,4},{8,5},{8,6},{8,7},{8,8},{8,9},
        {9,9},{9,8},{9,7},{9,6},{9,5},{9,4},{9,3},{9,2},{9,1},{9,0}
    };
    
    for (int round = 0; round < MAX_ROUNDS && operations.size() < T; round++) {
        for (int i = 0; i < 100 && operations.size() < T; i++) {
            int targetR = route[i].first;
            int targetC = route[i].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 {
                    operations.push_back('L');
                    currentC--;
                }
            }
            
            if (operations.size() >= T) break;
            
            // アクション生成
            if (sol.actions[i].getCopy(round) && operations.size() < T) {
                operations.push_back('C');
            }
            
            if (sol.actions[i].getWrite(round) && operations.size() < T) {
                operations.push_back('W');
            }
        }
    }
    
    return operations;
}

// ===== メイン処理 =====
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];
        }
    }
}

int main() {
    // 最適化バージョンの表示
    cerr << "Portable Optimized Version - No SIMD" << endl;
    
    auto start_time = chrono::high_resolution_clock::now();
    rng.seed(chrono::duration_cast<chrono::nanoseconds>(start_time.time_since_epoch()).count());
    
    input();
    
    cerr << "N=" << N << ", T=" << T << ", Grid size=" << N*N << endl;
    cerr << "Max rounds=" << MAX_ROUNDS << ", Time limit=" << TIME_LIMIT << "s" << endl;
    
    TurboOptimizer optimizer;
    FastSolution bestSolution = optimizer.optimize();
    vector<char> operations = generateFastOperations(bestSolution);
    
    for (char op : operations) {
        cout << op << endl;
    }
    
    return 0;
}