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

提出ソース
結果

問題	No.5022 XOR Printer
ユーザー	ぴぃいいいい
提出日時	2025-07-30 01:03:57
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,953 ms / 2,000 ms
コード長	12,287 bytes
コンパイル時間	2,617 ms
コンパイル使用メモリ	211,008 KB
実行使用メモリ	7,716 KB
スコア	5,203,882,686
最終ジャッジ日時	2025-07-30 01:05:42
合計ジャッジ時間	104,685 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 50
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <algorithm>
#include <climits>
#include <chrono>
#include <random>

using namespace std;

// 定数定義
const int GRID_SZ = 10;
const int TOTAL_CELLS = 100;
const int HALF_CELLS = 50;
const int BITS_CNT = 20;
const int EMERG_THRESH = 20;
const int GRID_MAX_IDX = 9;
const int SNAKE_W = 5;
const double TIME_LIMIT = 1.95; // 実行時間制限（秒）

// 操作タイプ
enum Command {
    COLLECT = 'C',  // 値を取得
    WRITE = 'W',    // 値を書き込み
    UP = 'U',       // 上移動
    DOWN = 'D',     // 下移動
    LEFT = 'L',     // 左移動
    RIGHT = 'R'     // 右移動
};

// 座標構造体
struct Position {
    int x, y;
    Position(int x = 0, int y = 0) : x(x), y(y) {}
    
    // マンハッタン距離を計算
    int distance_to(const Position& other) const {
        return abs(x - other.x) + abs(y - other.y);
    }
};

// ソリューション結果を格納する構造体
struct SolutionResult {
    vector<Command> operations;
    long long final_score;
    int operations_count;
    
    SolutionResult() : final_score(0), operations_count(0) {}
};

// グローバル変数
int n, t_limit;
int original_a[GRID_SZ][GRID_SZ];     // 元のグリッド値（バックアップ用）
Position route[TOTAL_CELLS];           // 事前計算されたルート
mt19937 rng;                          // 乱数生成器
chrono::high_resolution_clock::time_point start_time;

// 関数宣言
void input();
Position calc_pos(int q);
SolutionResult solve_once(int seed);
long long calculate_final_score(const int grid[GRID_SZ][GRID_SZ]);
vector<Position> solve_tsp_randomized(const vector<Position>& targets, const Position& current_pos, mt19937& gen);
bool two_opt_improve(vector<Position>& route, mt19937& gen);
int calculate_total_distance(const vector<Position>& route, const Position& start);

// 時間チェック関数
bool is_time_limit_reached() {
    auto current_time = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration<double>(current_time - start_time).count();
    return elapsed >= TIME_LIMIT;
}

// 最終スコアを計算
long long calculate_final_score(const int grid[GRID_SZ][GRID_SZ]) {
    long long score = 0;
    for (int i = 0; i < GRID_SZ; ++i) {
        for (int j = 0; j < GRID_SZ; ++j) {
            score += grid[i][j];
        }
    }
    return score;
}

// インデックスから座標を計算する関数
Position calc_pos(int q) {
    if (q >= HALF_CELLS) {
        // 後半50個は前半の鏡像
        Position pos = calc_pos(q - HALF_CELLS);
        return Position(GRID_MAX_IDX - pos.x, GRID_MAX_IDX - pos.y);
    } else {
        // 前半50個の座標計算（蛇行パターン）
        int x = q / SNAKE_W;
        int y = (q / SNAKE_W % 2) ? (q % SNAKE_W) : (SNAKE_W - 1 - q % SNAKE_W);
        return Position(x, y);
    }
}

// ルートの総距離を計算
int calculate_total_distance(const vector<Position>& route, const Position& start) {
    if (route.size() <= 1) return 0;
    
    int total = start.distance_to(route[0]);  // スタート地点から最初の点まで
    
    for (size_t i = 0; i < route.size() - 1; ++i) {
        total += route[i].distance_to(route[i + 1]);
    }
    
    return total;
}

// 2-opt改善を実行（ランダムな探索順序）
bool two_opt_improve(vector<Position>& route, mt19937& gen) {
    bool improved = false;
    int n = route.size();
    
    // i,jのペアをランダムな順序で探索
    vector<pair<int, int>> pairs;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 2; j < n; ++j) {
            pairs.push_back({i, j});
        }
    }
    
    // ペアをランダムにシャッフル
    shuffle(pairs.begin(), pairs.end(), gen);
    
    for (const auto& p : pairs) {
        int i = p.first;
        int j = p.second;
        
        // 元の距離
        int old_dist = route[i].distance_to(route[i + 1]) + route[j].distance_to(route[(j + 1) % n]);
        
        // 2-opt交換後の距離
        int new_dist = route[i].distance_to(route[j]) + route[i + 1].distance_to(route[(j + 1) % n]);
        
        if (new_dist < old_dist) {
            // 区間 [i+1, j] を逆順にする
            reverse(route.begin() + i + 1, route.begin() + j + 1);
            improved = true;
        }
    }
    
    return improved;
}

// ランダム性を持たせたTSP解決
vector<Position> solve_tsp_randomized(const vector<Position>& targets, const Position& current_pos, mt19937& gen) {
    if (targets.empty()) return vector<Position>();
    if (targets.size() == 1) return targets;
    
    vector<Position> result;
    vector<bool> visited(targets.size(), false);
    
    // 現在地から最も近い点を開始点とする
    int current_idx = 0;
    int min_distance = INT_MAX;
    for (size_t i = 0; i < targets.size(); ++i) {
        int distance = current_pos.distance_to(targets[i]);
        if (distance < min_distance) {
            min_distance = distance;
            current_idx = i;
        }
    }
    
    visited[current_idx] = true;
    result.push_back(targets[current_idx]);
    
    // 貪欲法でTSPを近似的に解く
    for (size_t count = 1; count < targets.size(); ++count) {
        vector<pair<int, int>> candidates; // {distance, index}
        
        for (size_t i = 0; i < targets.size(); ++i) {
            if (!visited[i]) {
                int distance = targets[current_idx].distance_to(targets[i]);
                candidates.push_back({distance, i});
            }
        }
        
        if (candidates.empty()) break;
        
        // 距離でソートし、最短距離を選択
        sort(candidates.begin(), candidates.end());
        
        int next_idx = candidates[0].second;
        visited[next_idx] = true;
        result.push_back(targets[next_idx]);
        current_idx = next_idx;
    }
    
    // 2-opt局所探索で改善
    int max_iterations = 1000;
    for (int iter = 0; iter < max_iterations; ++iter) {
        if (!two_opt_improve(result, gen)) {
            break;
        }
    }
    
    return result;
}

// 一度のソリューション実行
SolutionResult solve_once(int seed) {
    SolutionResult result;
    
    // 乱数生成器を初期化
    mt19937 local_rng(seed);
    
    // グリッドをコピー
    int a[GRID_SZ][GRID_SZ];
    for (int i = 0; i < GRID_SZ; ++i) {
        for (int j = 0; j < GRID_SZ; ++j) {
            a[i][j] = original_a[i][j];
        }
    }
    
    int s = 0;  // 現在のスコア状態
    int t = t_limit;  // 残り操作回数
    Position cur_pos(0, 0);  // 現在位置
    
    // ビット順序は上位ビットから固定順序で処理
    
    auto move_to = [&](const Position& target) {
        while (cur_pos.x < target.x) {
            ++cur_pos.x;
            result.operations.push_back(DOWN);
            if (++result.operations_count >= t_limit) return;
        }
        while (cur_pos.x > target.x) {
            --cur_pos.x;
            result.operations.push_back(UP);
            if (++result.operations_count >= t_limit) return;
        }
        while (cur_pos.y < target.y) {
            ++cur_pos.y;
            result.operations.push_back(RIGHT);
            if (++result.operations_count >= t_limit) return;
        }
        while (cur_pos.y > target.y) {
            --cur_pos.y;
            result.operations.push_back(LEFT);
            if (++result.operations_count >= t_limit) return;
        }
    };
    
    auto find_nearest_bit_target = [&](int bit) -> Position {
        Position best_pos(-1, -1);
        int min_distance = INT_MAX;
        
        for (int q = 0; q < TOTAL_CELLS; ++q) {
            Position pos = route[q];
            
            if ((s ^ a[pos.x][pos.y]) >> bit == 1) {
                int distance = cur_pos.distance_to(pos);
                if (distance < min_distance) {
                    min_distance = distance;
                    best_pos = pos;
                }
            }
        }
        
        return best_pos;
    };
    
    // ビット位置ごとの処理（上位ビットから）
    for (int b = BITS_CNT - 1; b >= 0; --b) {
        if (result.operations_count >= t_limit - EMERG_THRESH) break;
        
        // ステップ1: ビットbを立てるための値を探す
        Position target_pos = find_nearest_bit_target(b);
        if (target_pos.x != -1) {
            move_to(target_pos);
            if (result.operations_count >= t_limit) break;
            result.operations.push_back(COLLECT);
            ++result.operations_count;
            s ^= a[target_pos.x][target_pos.y];
        }
        
        // ビットbが立っていない場合はスキップ
        if ((s >> b) != 1) {
            continue;
        }
        
        // ステップ2: ビットbが0の箇所を列挙
        vector<Position> write_targets;
        for (int q = 0; q < TOTAL_CELLS; ++q) {
            Position pos = route[q];
            if (pos.x >= 0 && pos.x < GRID_SZ && pos.y >= 0 && pos.y < GRID_SZ) {
                if (!(a[pos.x][pos.y] >> b & 1)) {
                    write_targets.push_back(pos);
                }
            }
        }
        
        // ステップ3: TSPで最適な巡回順序を決定
        if (write_targets.size() > 0) {
            vector<Position> optimal_order = solve_tsp_randomized(write_targets, cur_pos, local_rng);
            
            // 最適順序でWRITE操作を実行
            for (const Position& pos : optimal_order) {
                if (result.operations_count >= t_limit - EMERG_THRESH) break;
                move_to(pos);
                if (result.operations_count >= t_limit) break;
                result.operations.push_back(WRITE);
                ++result.operations_count;
                a[pos.x][pos.y] ^= s;
            }
        }
        
        // 特定位置での追加処理
        if (b < BITS_CNT - 1 && result.operations_count < t_limit - EMERG_THRESH) {
            int idx = TOTAL_CELLS - (BITS_CNT - 1 - b);
            Position pos = route[idx];
            
            move_to(pos);
            if (result.operations_count < t_limit) {
                result.operations.push_back(WRITE);
                ++result.operations_count;
                a[pos.x][pos.y] ^= s;
                result.operations.push_back(COLLECT);
                ++result.operations_count;
                s ^= a[pos.x][pos.y];
            }
        }
    }
    
    result.final_score = calculate_final_score(a);
    return result;
}

// 入力を受け取る関数
void input() {
    cin >> n >> t_limit;
    
    for (int i = 0; i < GRID_SZ; ++i) {
        for (int j = 0; j < GRID_SZ; ++j) {
            cin >> original_a[i][j];
        }
    }
}

int main() {
    start_time = chrono::high_resolution_clock::now();
    
    input();
    
    // ルートの事前計算
    for (int q = 0; q < TOTAL_CELLS; ++q) {
        route[q] = calc_pos(q);
    }
    
    // 乱数生成器を初期化
    random_device rd;
    rng.seed(rd());
    
    SolutionResult best_solution;
    int iteration = 0;
    
    // 時間制限まで複数回実行
    while (!is_time_limit_reached()) {
        int seed = rng();
        SolutionResult current_solution = solve_once(seed);
        
        if (current_solution.final_score > best_solution.final_score) {
            best_solution = current_solution;
            fprintf(stderr, "Iteration %d: New best score = %lld (operations: %d)\n", 
                   iteration, best_solution.final_score, best_solution.operations_count);
        }
        
        ++iteration;
        
        // 最小でも1回は実行する
        if (iteration == 1 && !is_time_limit_reached()) {
            continue;
        }
    }
    
    // 最良解を出力
    for (Command cmd : best_solution.operations) {
        putchar(static_cast<char>(cmd));
        putchar('\n');
    }
    
    fprintf(stderr, "Total iterations: %d\n", iteration);
    fprintf(stderr, "Best score: %lld\n", best_solution.final_score);
    fprintf(stderr, "Operations used: %d/%d\n", best_solution.operations_count, t_limit);
    
    return 0;
}
yukicoder

結果

ソースコード
