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

• 問題: No.5022 XOR Printer
• ユーザー: ぴぃいいいい
• 提出日時: 2025-07-29 07:51:58
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,084 ms / 2,000 ms
• コード長: 23,105 bytes
• コンパイル時間: 3,021 ms
• コンパイル使用メモリ: 220,368 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,850,775,447
• 最終ジャッジ日時: 2025-07-29 07:53:00
• 合計ジャッジ時間: 60,944 ms
• ジャッジサーバーID （参考情報）: judge5 / 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;
constexpr int MAX_BITS = 20;
constexpr double TIME_LIMIT = 1.8;

// ===== Phase 1: main7.cppの手順で上2桁を1で揃える =====

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

inline bool hasBit(int value, int bit_pos) {
    return (value >> bit_pos) & 1;
}

int countMissingBits(const vector<vector<int>>& grid, int bit_pos) {
    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!hasBit(grid[i][j], bit_pos)) {
                count++;
            }
        }
    }
    return count;
}

// Phase 1: main7.cppと同じビット単位充填戦略（bit 19, 18のみ）
struct Phase1Result {
    vector<char> operations;
    pair<int, int> end_position;
    vector<vector<int>> grid_state;
    int s_value;
    long long score;
};

Phase1Result phase1_bitWiseFill() {
    auto start_time = chrono::high_resolution_clock::now();
    vector<char> operations;
    operations.reserve(T);
    
    cerr << "=== Phase 1: Bit-wise Fill Strategy ===" << endl;
    
    // 蛇行ルートを事前計算
    vector<pair<int, int>> route;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            for (int j = 0; j < N; j++) {
                route.push_back({i, j});
            }
        } else {
            for (int j = N - 1; j >= 0; j--) {
                route.push_back({i, j});
            }
        }
    }
    
    int currentR = 0, currentC = 0;
    int s = 0;
    
    // 高位ビット（bit 19, 18）のみ処理
    for (int bit = MAX_BITS - 1; bit >= 18; bit--) {
        // 最初のビット（bit 19）の場合、sを初期化
        if (bit == MAX_BITS - 1 && s == 0) {
            bool initialized = false;
            for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
                int r = route[idx].first;
                int c = route[idx].second;
                
                if (hasBit(A[r][c], bit)) {
                    // このマスに移動
                    while ((currentR != r || currentC != c) && operations.size() < T) {
                        if (currentR < r) {
                            operations.push_back('D');
                            currentR++;
                        } else if (currentR > r) {
                            operations.push_back('U');
                            currentR--;
                        } else if (currentC < c) {
                            operations.push_back('R');
                            currentC++;
                        } else {
                            operations.push_back('L');
                            currentC--;
                        }
                    }
                    
                    if (operations.size() >= T) break;
                    
                    operations.push_back('C');
                    s ^= A[r][c];
                    initialized = true;
                    break;
                }
            }
            
            if (!initialized) continue;
        }
        
        auto current_time = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(current_time - start_time).count();
        
        if (elapsed >= TIME_LIMIT * 0.4) { // Phase1は40%の時間を使用
            cerr << "Phase 1 time limit reached at bit " << bit << endl;
            break;
        }
        
        if (operations.size() >= T - 200) { // Phase2用に200操作を残す
            cerr << "Phase 1 operation limit reached at bit " << bit << endl;
            break;
        }
        
        int missing_before = countMissingBits(A, bit);
        if (missing_before == 0) continue;
        
        cerr << "Processing bit " << bit << " (" << missing_before << " cells missing)" << endl;
        
        // XOR戦略で上位ビットをクリア
        for (int upper_bit = MAX_BITS - 1; upper_bit > bit; upper_bit--) {
            if (hasBit(s, upper_bit) && operations.size() < T - 150) {
                bool found = false;
                for (int idx = 0; idx < route.size() && operations.size() < T - 100; idx++) {
                    int r = route[idx].first;
                    int c = route[idx].second;
                    
                    if (hasBit(A[r][c], upper_bit)) {
                        while ((currentR != r || currentC != c) && operations.size() < T) {
                            if (currentR < r) {
                                operations.push_back('D');
                                currentR++;
                            } else if (currentR > r) {
                                operations.push_back('U');
                                currentR--;
                            } else if (currentC < c) {
                                operations.push_back('R');
                                currentC++;
                            } else {
                                operations.push_back('L');
                                currentC--;
                            }
                        }
                        
                        if (operations.size() >= T) break;
                        
                        operations.push_back('C');
                        s ^= A[r][c];
                        found = true;
                        break;
                    }
                }
                
                if (!found) break;
            }
        }
        
        // 目標ビットを設定
        if (!hasBit(s, bit) && operations.size() < T - 100) {
            bool found = false;
            for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
                int r = route[idx].first;
                int c = route[idx].second;
                
                if (hasBit(A[r][c], bit)) {
                    while ((currentR != r || currentC != c) && operations.size() < T) {
                        if (currentR < r) {
                            operations.push_back('D');
                            currentR++;
                        } else if (currentR > r) {
                            operations.push_back('U');
                            currentR--;
                        } else if (currentC < c) {
                            operations.push_back('R');
                            currentC++;
                        } else {
                            operations.push_back('L');
                            currentC--;
                        }
                    }
                    
                    if (operations.size() >= T) break;
                    
                    operations.push_back('C');
                    s ^= A[r][c];
                    found = true;
                    break;
                }
            }
            
            if (!found) break;
        }
        
        // 各セルを巡回して書き込み
        int filled_count = 0;
        for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
            int r = route[idx].first;
            int c = route[idx].second;
            
            if (!hasBit(A[r][c], bit)) {
                while ((currentR != r || currentC != c) && operations.size() < T) {
                    if (currentR < r) {
                        operations.push_back('D');
                        currentR++;
                    } else if (currentR > r) {
                        operations.push_back('U');
                        currentR--;
                    } else if (currentC < c) {
                        operations.push_back('R');
                        currentC++;
                    } else {
                        operations.push_back('L');
                        currentC--;
                    }
                }
                
                if (operations.size() >= T) break;
                
                operations.push_back('W');
                A[r][c] ^= s;
                filled_count++;
            }
        }
        
        int missing_after = countMissingBits(A, bit);
        cerr << "Bit " << bit << " processed: " << missing_before << " -> " << missing_after << " missing" << endl;
    }
    
    long long phase1_score = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            phase1_score += A[i][j];
        }
    }
    
    cerr << "Phase 1 complete: " << operations.size() << " operations, score: " << phase1_score << endl;
    
    // Phase1の結果をまとめて返す
    Phase1Result result;
    result.operations = operations;
    result.end_position = {currentR, currentC};
    result.grid_state = A; // Phase1完了後のグリッド状態
    result.s_value = s;    // Phase1完了後のs値
    result.score = phase1_score;
    
    return result;
}

// ===== Phase 2: 順序最適化連続巡回焼きなまし =====

// 高速乱数生成器
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);
}

// 連続巡回ルート生成
vector<pair<int, int>> generateContinuousRoute() {
    vector<pair<int, int>> route;
    
    cerr << "=== Generating Continuous Circuit Route ===" << endl;
    
    for (int circuit = 0; circuit < 10; circuit++) {
        if (circuit == 0) {
            // 最初の周回は通常の蛇行
            for (int i = 0; i < N; i++) {
                if (i % 2 == 0) {
                    for (int j = 0; j < N; j++) {
                        route.push_back({i, j});
                    }
                } else {
                    for (int j = N - 1; j >= 0; j--) {
                        route.push_back({i, j});
                    }
                }
            }
            cerr << "Circuit " << circuit << ": (0,0)→...→(9,0)" << endl;
        } else {
            if (circuit % 2 == 1) {
                // 奇数周回: 下から上へ、右から左へ蛇行
                for (int i = N-1; i >= 0; i--) {
                    if ((N-1-i) % 2 == 0) {
                        for (int j = N-1; j >= 0; j--) {
                            route.push_back({i, j});
                        }
                    } else {
                        for (int j = 0; j < N; j++) {
                            route.push_back({i, j});
                        }
                    }
                }
                cerr << "Circuit " << circuit << ": (9,0)→...→(0,9)" << endl;
            } else {
                // 偶数周回: 上から下へ、左から右へ蛇行
                for (int i = 0; i < N; i++) {
                    if (i % 2 == 0) {
                        for (int j = 0; j < N; j++) {
                            route.push_back({i, j});
                        }
                    } else {
                        for (int j = N - 1; j >= 0; j--) {
                            route.push_back({i, j});
                        }
                    }
                }
                cerr << "Circuit " << circuit << ": (0,9)→...→(9,0)" << endl;
            }
        }
    }
    
    cerr << "Total route points: " << route.size() << " (" << route.size()/100 << " circuits)" << endl;
    
    return route;
}

// 順序最適化アクション構造
constexpr int MAX_ROUTE_POINTS = 1000;

enum ActionOrder {
    NONE = 0,           // 何もしない
    COPY_ONLY = 1,      // コピーのみ
    WRITE_ONLY = 2,     // 書き込みのみ
    COPY_THEN_WRITE = 3, // コピー→書き込み
    WRITE_THEN_COPY = 4  // 書き込み→コピー
};

struct OrderOptimizedAction {
    ActionOrder order;
    
    OrderOptimizedAction() : order(NONE) {}
    
    bool hasCopy() const {
        return order == COPY_ONLY || order == COPY_THEN_WRITE || order == WRITE_THEN_COPY;
    }
    
    bool hasWrite() const {
        return order == WRITE_ONLY || order == COPY_THEN_WRITE || order == WRITE_THEN_COPY;
    }
    
    bool copyFirst() const {
        return order == COPY_THEN_WRITE;
    }
    
    bool writeFirst() const {
        return order == WRITE_THEN_COPY;
    }
};

struct OrderOptimizedSolution {
    OrderOptimizedAction actions[MAX_ROUTE_POINTS];
    long long score;
    
    OrderOptimizedSolution() : score(0) {}
};

// Phase 2: 順序最適化連続巡回焼きなまし法
vector<char> phase2_orderOptimizedSimulatedAnnealing(const Phase1Result& phase1_result) {
    auto start_time = chrono::high_resolution_clock::now();
    
    int remaining_ops = T - phase1_result.operations.size();
    cerr << "=== Phase 2: Order-Optimized Continuous Circuit SA ===" << endl;
    cerr << "Remaining operations: " << remaining_ops << endl;
    
    xorshift_state = chrono::high_resolution_clock::now().time_since_epoch().count();
    
    // 連続巡回ルート生成
    vector<pair<int, int>> route = generateContinuousRoute();
    
    // 初期解生成（順序も考慮）
    OrderOptimizedSolution current;
    for (int i = 0; i < MAX_ROUTE_POINTS; i++) {
        double rand_val = fastRandom();
        if (rand_val < 0.15) {
            current.actions[i].order = COPY_ONLY;
        } else if (rand_val < 0.30) {
            current.actions[i].order = WRITE_ONLY;
        } else if (rand_val < 0.50) {
            current.actions[i].order = COPY_THEN_WRITE;
        } else if (rand_val < 0.70) {
            current.actions[i].order = WRITE_THEN_COPY;
        } else {
            current.actions[i].order = NONE;
        }
    }
    
    // Phase1の状態を使ってスコア計算（順序考慮）
    auto calculateScore = [&](const OrderOptimizedSolution& sol) -> long long {
        // Phase1の結果からスタート
        A = phase1_result.grid_state;
        int s = phase1_result.s_value;
        int currentR = phase1_result.end_position.first;
        int currentC = phase1_result.end_position.second;
        int ops_used = 0;
        
        // 連続巡回実行（順序最適化）
        for (int i = 0; i < route.size() && ops_used < remaining_ops; i++) {
            int targetR = route[i].first;
            int targetC = route[i].second;
            
            // 移動コスト計算
            int move_ops = abs(currentR - targetR) + abs(currentC - targetC);
            ops_used += move_ops;
            currentR = targetR;
            currentC = targetC;
            
            if (ops_used >= remaining_ops) break;
            
            // 順序最適化アクション実行
            ActionOrder order = sol.actions[i].order;
            
            if (order == COPY_ONLY && ops_used < remaining_ops) {
                ops_used++;
                s ^= A[currentR][currentC];
            }
            else if (order == WRITE_ONLY && ops_used < remaining_ops) {
                ops_used++;
                A[currentR][currentC] ^= s;
            }
            else if (order == COPY_THEN_WRITE && ops_used + 1 < remaining_ops) {
                // コピー→書き込みの順序
                ops_used++;
                s ^= A[currentR][currentC];
                ops_used++;
                A[currentR][currentC] ^= s;
            }
            else if (order == WRITE_THEN_COPY && ops_used + 1 < remaining_ops) {
                // 書き込み→コピーの順序
                ops_used++;
                A[currentR][currentC] ^= s;
                ops_used++;
                s ^= A[currentR][currentC];
            }
            // NONE の場合は何もしない
        }
        
        long long total = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                total += A[i][j];
            }
        }
        return total;
    };
    
    current.score = calculateScore(current);
    OrderOptimizedSolution best = current;
    
    int iter = 0;
    int improvements = 0;
    int order_changes = 0;
    
    // 順序最適化統計
    int action_stats[5] = {0}; // NONE, COPY_ONLY, WRITE_ONLY, COPY_THEN_WRITE, WRITE_THEN_COPY
    
    // 最適化された焼きなまし法
    while (true) {
        auto current_time = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(current_time - start_time).count();
        double total_elapsed = chrono::duration<double>(current_time - start_time).count();
        
        if (total_elapsed >= TIME_LIMIT * 0.95) break;
        
        double progress = elapsed / (TIME_LIMIT * 0.6);
        if (progress >= 1.0) break;
        
        // 最適化された温度設定（初期温度*pow(最終温度/初期温度,progress)）
        double initial_temp = 100000.0;
        double final_temp = 10000.0;
        double temp = initial_temp * pow(final_temp / initial_temp, progress);
        
        // 近傍生成（順序も含めて変更）
        OrderOptimizedSolution neighbor = current;
        int point = xorshift64() % MAX_ROUTE_POINTS;
        
        // 順序を含む近傍生成
        ActionOrder old_order = neighbor.actions[point].order;
        ActionOrder new_order;
        
        // ランダムに新しい順序を選択（現在と異なるもの）
        do {
            int rand_choice = xorshift64() % 5;
            new_order = static_cast<ActionOrder>(rand_choice);
        } while (new_order == old_order);
        
        neighbor.actions[point].order = new_order;
        
        neighbor.score = calculateScore(neighbor);
        double delta = neighbor.score - current.score;
        
        bool accept = false;
        if (delta > 0) {
            accept = true;
            improvements++;
            if (old_order != new_order) order_changes++;
        } else if (temp > 0.1) {
            accept = (fastRandom() < exp(delta / temp));
        }
        
        if (accept) {
            current = neighbor;
            if (current.score > best.score) {
                best = current;
            }
        }
        
        if (iter % 10000 == 0) {
            cerr << "SA iter: " << iter << ", temp: " << temp << ", best: " << best.score << ", order_changes: " << order_changes << endl;
        }
        
        iter++;
    }
    
    // 最終統計
    for (int i = 0; i < MAX_ROUTE_POINTS; i++) {
        action_stats[best.actions[i].order]++;
    }
    
    cerr << "Phase 2 complete: " << iter << " iterations, " << improvements << " improvements, " << order_changes << " order changes" << endl;
    cerr << "Best order-optimized score: " << best.score << endl;
    cerr << "Action distribution: NONE=" << action_stats[0] << ", COPY=" << action_stats[1] 
         << ", WRITE=" << action_stats[2] << ", C→W=" << action_stats[3] << ", W→C=" << action_stats[4] << endl;
    
    // 最適解を適用して操作列を生成
    vector<char> operations = phase1_result.operations;
    
    // Phase2の順序最適化連続巡回操作を追加
    A = phase1_result.grid_state;
    int s = phase1_result.s_value;
    int currentR = phase1_result.end_position.first;
    int currentC = phase1_result.end_position.second;
    
    // 連続巡回の操作生成（順序最適化）
    for (int i = 0; i < route.size() && 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;
        
        // 順序最適化アクション実行
        ActionOrder order = best.actions[i].order;
        
        if (order == COPY_ONLY && operations.size() < T) {
            operations.push_back('C');
            s ^= A[currentR][currentC];
        }
        else if (order == WRITE_ONLY && operations.size() < T) {
            operations.push_back('W');
            A[currentR][currentC] ^= s;
        }
        else if (order == COPY_THEN_WRITE && operations.size() + 1 < T) {
            operations.push_back('C');
            s ^= A[currentR][currentC];
            operations.push_back('W');
            A[currentR][currentC] ^= s;
        }
        else if (order == WRITE_THEN_COPY && operations.size() + 1 < T) {
            operations.push_back('W');
            A[currentR][currentC] ^= s;
            operations.push_back('C');
            s ^= A[currentR][currentC];
        }
        // NONE の場合は何もしない
    }
    
    cerr << "Generated " << operations.size() << " total operations (Phase1: " << phase1_result.operations.size() << ", Phase2: " << (operations.size() - phase1_result.operations.size()) << ")" << endl;
    
    // 最終スコア確認
    long long final_score = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            final_score += A[i][j];
        }
    }
    cerr << "Final grid score: " << final_score << endl;
    
    // 順序最適化効果の分析
    int total_double_actions = action_stats[3] + action_stats[4]; // C→W + W→C
    int total_single_actions = action_stats[1] + action_stats[2]; // COPY + WRITE
    cerr << "Order optimization: " << total_double_actions << " double actions, " << total_single_actions << " single actions" << endl;
    
    return operations;
}

int main() {
    cerr << "Order-Optimized Continuous Circuit Strategy - main10.cpp" << endl;
    
    input();
    
    cerr << "N=" << N << ", T=" << T << ", Grid size=" << N*N << endl;
    cerr << "Time limit=" << TIME_LIMIT << "s" << endl;
    
    if (N == 0 || T == 0) {
        cerr << "Error: N or T is 0. Input reading failed." << endl;
        return 1;
    }
    
    // Phase 1: main7.cppの手順で上2桁を1で揃える
    Phase1Result phase1_result = phase1_bitWiseFill();
    
    // Phase 2: 順序最適化連続巡回焼きなましを実行
    vector<char> final_operations = phase2_orderOptimizedSimulatedAnnealing(phase1_result);
    
    // 最終結果出力
    cerr << "=== Final Result ===" << endl;
    cerr << "Total operations: " << final_operations.size() << "/" << T << endl;
    cerr << "Phase1 score: " << phase1_result.score << endl;
    
    for (char op : final_operations) {
        cout << op << endl;
    }
    
    return 0;
}