結果

問題 No.5022 XOR Printer
ユーザー ぴぃいいいい
提出日時 2025-07-30 19:12:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 19,071 bytes
コンパイル時間 3,039 ms
コンパイル使用メモリ 224,580 KB
実行使用メモリ 70,040 KB
スコア 726,822,573
最終ジャッジ日時 2025-07-30 19:14:01
合計ジャッジ時間 80,585 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 7 TLE * 37 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <algorithm>
#include <climits>
#include <chrono>
#include <random>
#include <queue>

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; // 実行時間制限(秒) 
const int INITIAL_BEAM_WIDTH = 10; // 初期ビーム幅
const int MIN_BEAM_WIDTH = 2;      // 最小ビーム幅  
const int MAX_BEAM_WIDTH = 5000;     // 最大ビーム幅

// 操作タイプ
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 State {
    int grid[GRID_SZ][GRID_SZ];  // グリッドの状態
    int s;                       // 現在の値
    Position pos;                // 現在位置
    vector<Command> ops;         // 操作履歴
    long long score;             // 現在のスコア
    int ops_cnt;                 // 操作数
    int current_bit;             // 現在処理中のビット
    long long evaluation_score;  // 評価関数用スコア
    
    State() : s(0), pos(0, 0), score(0), ops_cnt(0), current_bit(BITS_CNT-1), evaluation_score(0) {
        for (int i = 0; i < GRID_SZ; ++i) {
            for (int j = 0; j < GRID_SZ; ++j) {
                grid[i][j] = 0;
            }
        }
    }
    
    // 状態をコピー
    State(const State& other) : s(other.s), pos(other.pos), ops(other.ops), 
                               score(other.score), ops_cnt(other.ops_cnt), 
                               current_bit(other.current_bit), evaluation_score(other.evaluation_score) {
        for (int i = 0; i < GRID_SZ; ++i) {
            for (int j = 0; j < GRID_SZ; ++j) {
                grid[i][j] = other.grid[i][j];
            }
        }
    }
    
    // スコア計算
    void calc_score() {
        score = 0;
        for (int i = 0; i < GRID_SZ; ++i) {
            for (int j = 0; j < GRID_SZ; ++j) {
                score += grid[i][j];
            }
        }
    }
    
    // 評価関数用スコア計算
    void calc_evaluation_score();  // 定義は外部で行う
};

// 状態の比較(評価関数で昇順ソート)
struct StateComparator {
    bool operator()(const State& a, const State& b) const {
        // 評価関数が小さい方が良い(昇順)のでprioriy_queueでは逆にする
        if (a.evaluation_score != b.evaluation_score) return a.evaluation_score > b.evaluation_score;
        return a.score < b.score; // 同じ評価なら最終スコアが高い方を優先
    }
};

// グローバル変数
int n, t_lim;
int orig_a[GRID_SZ][GRID_SZ];     // 元のグリッド値(バックアップ用)
Position rt[TOTAL_CELLS];           // 事前計算されたルート
mt19937 rng;                          // 乱数生成器
chrono::high_resolution_clock::time_point start_tm;

// 関数宣言
void input();
Position calc_pos(int q);
long long calc_score(const int grid[GRID_SZ][GRID_SZ]);
vector<Position> solve_tsp_rand(const vector<Position>& tgts, const Position& cur_pos, mt19937& gen);
bool two_opt_improve(vector<Position>& rt, mt19937& gen);
int calc_total_dist(const vector<Position>& rt, const Position& start);
bool progress_bit(int bit, State& state, mt19937& rng);
State beam_search();
void emergency_finish(State& state);
int calculate_dynamic_beam_width(int current_bit);

// 評価関数用スコア計算の実装
void State::calc_evaluation_score() {
    // 次に揃えるビットが0であるマスの数をカウント
    int zero_bit_count = 0;
    int next_bit = current_bit - 1; // 次に処理するビット
    
    if (next_bit >= 0) {
        for (int q = 0; q < TOTAL_CELLS; ++q) {
            Position pos = rt[q];
            if (pos.x >= 0 && pos.x < GRID_SZ && pos.y >= 0 && pos.y < GRID_SZ) {
                if (!(grid[pos.x][pos.y] >> next_bit & 1)) { // 次のビットが0
                    zero_bit_count++;
                }
            }
        }
    }
    
    // 評価関数: 操作回数 + 次ビットが0のマス数 (小さい方が良い)
    evaluation_score = ops_cnt + zero_bit_count;
}

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

// 動的ビーム幅計算
int calculate_dynamic_beam_width(int current_bit) {
    auto cur_tm = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration<double>(cur_tm - start_tm).count();
    double remaining_time = TIME_LIMIT - elapsed;
    int remaining_bits = current_bit + 1; // 残りビット数(0からcurrent_bitまで)
    
    // 残り時間とビット数から適切なビーム幅を計算
    if (remaining_time < 0.1) {
        return MIN_BEAM_WIDTH; // 時間がほとんどない場合
    }
    
    // 残り時間が十分ある場合は大きなビーム幅を使用
    if (remaining_time > 1.0) {
        return MAX_BEAM_WIDTH;
    }
    
    // 時間に比例してビーム幅を調整
    double time_ratio = remaining_time / 1.0; // 1秒を基準
    int beam_width = MIN_BEAM_WIDTH + (int)((MAX_BEAM_WIDTH - MIN_BEAM_WIDTH) * time_ratio);
    
    // 残りビット数も考慮(ビット数が少ない場合はビーム幅を小さく)
    if (remaining_bits < 5) {
        beam_width = min(beam_width, MIN_BEAM_WIDTH + 2);
    }
    
    return max(MIN_BEAM_WIDTH, min(MAX_BEAM_WIDTH, beam_width));
}

// インデックスから座標を計算する関数
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 calc_total_dist(const vector<Position>& rt, const Position& start) {
    if (rt.size() <= 1) return 0;
    
    int total = start.distance_to(rt[0]);  // スタート地点から最初の点まで
    
    for (size_t i = 0; i < rt.size() - 1; ++i) {
        total += rt[i].distance_to(rt[i + 1]);
    }
    
    return total;
}

// 2-opt改善を実行(ランダムな探索順序)
bool two_opt_improve(vector<Position>& rt, mt19937& gen) {
    bool improved = false;
    int n = rt.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 = rt[i].distance_to(rt[i + 1]) + rt[j].distance_to(rt[(j + 1) % n]);
        
        // 2-opt交換後の距離
        int new_dist = rt[i].distance_to(rt[j]) + rt[i + 1].distance_to(rt[(j + 1) % n]);
        
        if (new_dist < old_dist) {
            // 区間 [i+1, j] を逆順にする
            reverse(rt.begin() + i + 1, rt.begin() + j + 1);
            improved = true;
        }
    }
    
    return improved;
}

// ランダム性を持たせたTSP解決
vector<Position> solve_tsp_rand(const vector<Position>& tgts, const Position& cur_pos, mt19937& gen) {
    if (tgts.empty()) return vector<Position>();
    if (tgts.size() == 1) return tgts;
    
    vector<Position> res;
    vector<bool> vis(tgts.size(), false);
    
    // 現在地から最も近い点を開始点とする
    int cur_idx = 0;
    int min_dist = INT_MAX;
    for (size_t i = 0; i < tgts.size(); ++i) {
        int dist = cur_pos.distance_to(tgts[i]);
        if (dist < min_dist) {
            min_dist = dist;
            cur_idx = i;
        }
    }
    
    vis[cur_idx] = true;
    res.push_back(tgts[cur_idx]);
    
    // 貪欲法でTSPを近似的に解く
    for (size_t cnt = 1; cnt < tgts.size(); ++cnt) {
        vector<pair<int, int>> cands; // {distance, index}
        
        for (size_t i = 0; i < tgts.size(); ++i) {
            if (!vis[i]) {
                int dist = tgts[cur_idx].distance_to(tgts[i]);
                cands.push_back({dist, i});
            }
        }
        
        if (cands.empty()) break;
        
        // 距離でソートし、最短距離を選択
        sort(cands.begin(), cands.end());
        
        int next_idx = cands[0].second;
        vis[next_idx] = true;
        res.push_back(tgts[next_idx]);
        cur_idx = next_idx;
    }
    
    // 2-opt局所探索で改善
    int max_iters = 1000; // ビームサーチでは計算時間を短縮
    for (int iter = 0; iter < max_iters; ++iter) {
        if (!two_opt_improve(res, gen)) {
            break;
        }
    }
    
    return res;
}

// 1ビットを揃える処理(状態を更新)
bool progress_bit(int bit, State& state, mt19937& rng) {
    // move_to機能をローカル関数として定義
    auto move_to = [&](const Position& tgt) -> bool {
        while (state.pos.x < tgt.x) {
            ++state.pos.x;
            state.ops.push_back(DOWN);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.x > tgt.x) {
            --state.pos.x;
            state.ops.push_back(UP);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.y < tgt.y) {
            ++state.pos.y;
            state.ops.push_back(RIGHT);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.y > tgt.y) {
            --state.pos.y;
            state.ops.push_back(LEFT);
            if (++state.ops_cnt >= t_lim) return false;
        }
        return true;
    };
    
    // 最近のビットターゲットを見つける機能
    auto find_nearest_bit_tgt = [&](int b) -> Position {
        Position best_pos(-1, -1);
        int min_dist = INT_MAX;
        
        for (int q = 0; q < TOTAL_CELLS; ++q) {
            Position pos = rt[q];
            
            if ((state.s ^ state.grid[pos.x][pos.y]) >> b == 1) {
                int dist = state.pos.distance_to(pos);
                if (dist < min_dist) {
                    min_dist = dist;
                    best_pos = pos;
                }
            }
        }
        
        return best_pos;
    };
    
    // 操作回数制限チェック
    if (state.ops_cnt >= t_lim - EMERG_THRESH) return false;
    
    // ステップ1: ビットを立てるための値を探す
    Position tgt_pos = find_nearest_bit_tgt(bit);
    if (tgt_pos.x != -1) {
        if (!move_to(tgt_pos)) return false;
        if (state.ops_cnt >= t_lim) return false;
        state.ops.push_back(COLLECT);
        ++state.ops_cnt;
        state.s ^= state.grid[tgt_pos.x][tgt_pos.y];
    }
    
    // ビットが立っていない場合はスキップ
    if ((state.s >> bit) != 1) {
        return true;
    }
    
    // ステップ2: ビットが0の箇所を列挙
    vector<Position> write_tgts;
    for (int q = 0; q < TOTAL_CELLS; ++q) {
        Position pos = rt[q];
        if (pos.x >= 0 && pos.x < GRID_SZ && pos.y >= 0 && pos.y < GRID_SZ) {
            if (!(state.grid[pos.x][pos.y] >> bit & 1)) {
                write_tgts.push_back(pos);
            }
        }
    }
    
    // ステップ3: TSPで最適な巡回順序を決定
    if (write_tgts.size() > 0) {
        vector<Position> opt_ord = solve_tsp_rand(write_tgts, state.pos, rng);
        
        // 最適順序でWRITE操作を実行
        for (const Position& pos : opt_ord) {
            if (state.ops_cnt >= t_lim - EMERG_THRESH) break;
            if (!move_to(pos)) return false;
            if (state.ops_cnt >= t_lim) return false;
            state.ops.push_back(WRITE);
            ++state.ops_cnt;
            state.grid[pos.x][pos.y] ^= state.s;
        }
    }
    
    // 特定位置での追加処理
    if (bit < BITS_CNT - 1 && state.ops_cnt < t_lim - EMERG_THRESH) {
        int idx = TOTAL_CELLS - (BITS_CNT - 1 - bit);
        Position pos = rt[idx];
        
        if (!move_to(pos)) return false;
        if (state.ops_cnt < t_lim) {
            state.ops.push_back(WRITE);
            ++state.ops_cnt;
            state.grid[pos.x][pos.y] ^= state.s;
            state.ops.push_back(COLLECT);
            ++state.ops_cnt;
            state.s ^= state.grid[pos.x][pos.y];
        }
    }
    
    return true;
}

// 緊急終了処理(main12.cppから移植)
void emergency_finish(State& state) {
    // move_to機能をローカル関数として定義
    auto move_to = [&](const Position& tgt) -> bool {
        while (state.pos.x < tgt.x) {
            ++state.pos.x;
            state.ops.push_back(DOWN);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.x > tgt.x) {
            --state.pos.x;
            state.ops.push_back(UP);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.y < tgt.y) {
            ++state.pos.y;
            state.ops.push_back(RIGHT);
            if (++state.ops_cnt >= t_lim) return false;
        }
        while (state.pos.y > tgt.y) {
            --state.pos.y;
            state.ops.push_back(LEFT);
            if (++state.ops_cnt >= t_lim) return false;
        }
        return true;
    };
    
    // 緊急時の特定位置で処理
    Position emerg_pos1(0, 5);
    Position emerg_pos2(0, 4);
    
    // 操作回数制限内で実行
    if (state.ops_cnt < t_lim - 6) { // 最低6操作必要
        if (move_to(emerg_pos1)) {
            state.ops.push_back(COLLECT);
            ++state.ops_cnt;
            state.s ^= state.grid[emerg_pos1.x][emerg_pos1.y];
            
            if (move_to(emerg_pos2)) {
                state.ops.push_back(COLLECT);
                ++state.ops_cnt;
                state.s ^= state.grid[emerg_pos2.x][emerg_pos2.y];
                
                if (move_to(emerg_pos1)) {
                    state.ops.push_back(WRITE);
                    ++state.ops_cnt;
                    state.grid[emerg_pos1.x][emerg_pos1.y] ^= state.s;
                }
            }
        }
    }
}

// ビームサーチの実行
State beam_search() {
    // 初期状態を作成
    State initial_state;
    for (int i = 0; i < GRID_SZ; ++i) {
        for (int j = 0; j < GRID_SZ; ++j) {
            initial_state.grid[i][j] = orig_a[i][j];
        }
    }
    initial_state.calc_score();
    initial_state.calc_evaluation_score(); // 初期状態でも評価関数を計算
    
    // ビーム(優先度付きキュー)
    priority_queue<State, vector<State>, StateComparator> beam;
    beam.push(initial_state);
    
    State best_state = initial_state;
    
    // 各ビットについて処理
    for (int bit = BITS_CNT - 1; bit >= 0 && !is_time_up(); --bit) {
        // 動的ビーム幅を計算
        int current_beam_width = calculate_dynamic_beam_width(bit);
        priority_queue<State, vector<State>, StateComparator> next_beam;
        
        // 現在のビームから次の状態を生成
        while (!beam.empty() && next_beam.size() < current_beam_width * 3) { // 多めに生成してから選択
            State current = beam.top();
            beam.pop();
            
            // 複数の乱数シードで異なる遷移を試す
            for (int seed_offset = 0; seed_offset < 10 && next_beam.size() < current_beam_width * 3; ++seed_offset) {
                State next_state = current; // 状態をコピー
                next_state.current_bit = bit; // 現在処理中のビットを設定
                mt19937 local_rng(rng() + seed_offset);
                
                if (progress_bit(bit, next_state, local_rng)) {
                    next_state.calc_score();
                    next_state.calc_evaluation_score(); // 評価関数を計算
                    next_beam.push(next_state);
                    
                    // 最良状態を更新
                    if (next_state.score > best_state.score) {
                        best_state = next_state;
                    }
                }
            }
        }
        
        // 次のビームを上位current_beam_width個に制限
        beam = priority_queue<State, vector<State>, StateComparator>();
        int count = 0;
        while (!next_beam.empty() && count < current_beam_width) {
            beam.push(next_beam.top());
            next_beam.pop();
            count++;
        }
        
        // デバッグ情報(時間と動的ビーム幅も表示)
        auto cur_tm = chrono::high_resolution_clock::now();
        auto elapsed = chrono::duration<double>(cur_tm - start_tm).count();
        fprintf(stderr, "Bit %d: Beam width = %d, Beam size = %d, Time = %.2fs, Best score = %lld, Best eval = %lld\n", 
                bit, current_beam_width, (int)beam.size(), elapsed, best_state.score, best_state.evaluation_score);
    }
    
    // 残り操作数が緊急閾値以下になった場合、緊急終了処理を実行
    if (best_state.ops_cnt >= t_lim - EMERG_THRESH) {
        fprintf(stderr, "Emergency finish triggered at ops_cnt = %d\n", best_state.ops_cnt);
        emergency_finish(best_state);
        best_state.calc_score(); // 最終スコアを再計算
    }
    
    return best_state;
}

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

int main() {
    start_tm = chrono::high_resolution_clock::now();
    
    input();
    
    // ルートの事前計算
    for (int q = 0; q < TOTAL_CELLS; ++q) {
        rt[q] = calc_pos(q);
    }
    
    // 乱数生成器を初期化
    random_device rd;
    rng.seed(rd());
    
    // ビームサーチを実行
    State best = beam_search();
    
    // 最良解を出力
    for (Command cmd : best.ops) {
        putchar(static_cast<char>(cmd));
        putchar('\n');
    }
    
    fprintf(stderr, "Best score: %lld\n", best.score);
    fprintf(stderr, "Operations used: %d/%d\n", best.ops_cnt, t_lim);
    
    return 0;
}
0