結果

問題 No.5022 XOR Printer
ユーザー e6nlaq
提出日時 2025-07-26 16:57:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,896 bytes
コンパイル時間 2,841 ms
コンパイル使用メモリ 200,720 KB
実行使用メモリ 8,588 KB
スコア 4,427,318,036
最終ジャッジ日時 2025-07-26 16:58:51
合計ジャッジ時間 82,710 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <map>
#include <set> // ビームサーチの重複状態管理に使えるかも
#include <chrono>

using namespace std;

// 定数
const int N = 10;
const int MAX_T = 1000;
const int MAX_BIT = 20;

// グリッドの状態
vector<vector<int>> initial_A_bs; // 初期グリッドを保持

// 盤面状態を保持する構造体 (ビームサーチ用)
struct BS_BoardState {
    vector<vector<int>> current_A;
    int current_r, current_c;
    int s_val;
    vector<string> operations;
    long long score; // 評価関数値

    // コンストラクタ
    BS_BoardState() : current_r(0), current_c(0), s_val(0), score(0) {}

    // 初期化
    void init(const vector<vector<int>>& initial_grid) {
        current_A = initial_grid;
        current_r = 0;
        current_c = 0;
        s_val = 0;
        operations.clear();
        score = calculate_score(); // 初期スコア計算
    }

    // 操作を適用して新しい状態を返す
    BS_BoardState apply_op_and_get_new_state(const string& op) const {
        BS_BoardState new_state = *this; // 現在の状態をコピー
        
        // 無効な操作のチェック
        if (op == "U" && new_state.current_r == 0) return new_state; // 変更しない
        if (op == "D" && new_state.current_r == N - 1) return new_state;
        if (op == "L" && new_state.current_c == 0) return new_state;
        if (op == "R" && new_state.current_c == N - 1) return new_state;
        
        new_state.operations.push_back(op);
        
        if (op == "U") new_state.current_r--;
        else if (op == "D") new_state.current_r++;
        else if (op == "L") new_state.current_c--;
        else if (op == "R") new_state.current_c++;
        else if (op == "W") new_state.current_A[new_state.current_r][new_state.current_c] ^= new_state.s_val;
        else if (op == "C") new_state.s_val ^= new_state.current_A[new_state.current_r][new_state.current_c];

        new_state.score = new_state.calculate_score(); // スコアを再計算
        return new_state;
    }

    // スコア計算 (constメソッドにする)
    long long calculate_score() const {
        long long current_score = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                current_score += current_A[i][j];
            }
        }
        return current_score;
    }
};

// スコアでソートするための比較関数 (ビームサーチ用)
bool compareBS_BoardStates(const BS_BoardState& a, const BS_BoardState& b) {
    return a.score > b.score; // スコアが高い方を優先
}

// ビームサーチのメイン関数
vector<string> beam_search(const vector<vector<int>>& initial_grid, int beam_width = 100) {
    vector<BS_BoardState> current_beam;

    BS_BoardState initial_state;
    initial_state.init(initial_grid);
    current_beam.push_back(initial_state);

    vector<string> best_operations = initial_state.operations;
    long long max_overall_score = initial_state.score;

    string possible_ops[] = {"U", "D", "L", "R", "W", "C"};

    for (int t = 0; t < MAX_T; ++t) {
        vector<BS_BoardState> next_beam;
        
        if (current_beam.empty()) break; // 探索するパスがなくなったら終了

        for (const auto& state : current_beam) {
            for (const string& op_str : possible_ops) {
                BS_BoardState new_state = state.apply_op_and_get_new_state(op_str);
                next_beam.push_back(new_state);
            }
        }

        // 次のビームをソートし、ビーム幅で刈り取る
        sort(next_beam.begin(), next_beam.end(), compareBS_BoardStates);
        
        // 重複状態の除去 (任意だが、効率改善のため)
        // map<tuple<vector<vector<int>>, int, int, int>, bool> visited;
        // vector<BS_BoardState> unique_next_beam;
        // for(const auto& state : next_beam) {
        //     // 状態を一意に識別するキーを作成 (A, r, c, s_val)
        //     // 注意: Aをキーに含めるとvector<vector<int>>はtupleに直接入れられないので、ハッシュ化など工夫が必要
        //     // あるいは、visitedを使わず、単にスコアで選ぶだけにする。
        //     unique_next_beam.push_back(state); // 今回は簡略化のためそのまま追加
        // }
        // next_beam = unique_next_beam;

        if (next_beam.size() > beam_width) {
            next_beam.resize(beam_width);
        }
        current_beam = next_beam;

        // 全体でのベストスコアを更新
        if (!current_beam.empty() && current_beam[0].score > max_overall_score) {
            max_overall_score = current_beam[0].score;
            best_operations = current_beam[0].operations;
        }
    }
    
    // 最終的なビームの中で最も良いものを選択
    if (!current_beam.empty()) {
        sort(current_beam.begin(), current_beam.end(), compareBS_BoardStates);
        if (current_beam[0].score > max_overall_score) {
            best_operations = current_beam[0].operations;
        }
    }

    return best_operations;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int dummy_N, dummy_T;
    cin >> dummy_N >> dummy_T;

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

    // どちらか一方を選択して呼び出す
    // vector<string> final_operations = simulated_annealing(initial_A_bs, 1900); // 1.9秒で実行
    vector<string> final_operations = beam_search(initial_A_bs, 50); // ビーム幅 200 (要調整)

    for (const string& op : final_operations) {
        cout << op << endl;
    }

    return 0;
}
0