結果
問題 |
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 |
ソースコード
#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; }