結果
| 問題 |
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;
}