結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 mtmr_s1
|
| 提出日時 | 2025-07-26 15:25:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,985 ms / 2,000 ms |
| コード長 | 13,368 bytes |
| コンパイル時間 | 1,792 ms |
| コンパイル使用メモリ | 129,828 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,113,451,154 |
| 最終ジャッジ日時 | 2025-07-26 15:27:40 |
| 合計ジャッジ時間 | 105,568 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <random>
#include <cmath>
using namespace std;
// --- パラメータ調整欄 ---
// --- 戦略パラメータ ---
// 序盤フェーズで訪問するターゲットの数 (全99個中)
const int INITIAL_PHASE_TARGETS = 80;
// 序盤フェーズで許容する最大マンハッタン距離
const int MAX_DIST_INITIAL_PHASE = 12;
// 後半戦略で「遠い」と判断するマンハッタン距離
const int MIN_DIST_FOR_TARGETING = 10;
// --- 焼きなましパラメータ ---
// 実行時間制限（ミリ秒）。2000msの制限に対し、マージンを持たせる
const double TIME_LIMIT_MS = 1980.0;
// 焼きなましの開始温度
const double SA_START_TEMP = 100000.0;
// 焼きなましの終了温度
const double SA_END_TEMP = 1.0;
// --- グローバル定数 (変更不要) ---
const int N_CONST = 10;
const int T_CONST = 1000;
// --- 乱数生成器 ---
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/**
* @struct State
* @brief 現在のゲームの状態を管理する構造体
*/
struct State {
int r, c;
int s;
vector<vector<int>> grid;
int ops_count;
string ops_log;
State(const vector<vector<int>>& initial_grid) {
r = 0; c = 0; s = 0;
grid = initial_grid;
ops_count = 0;
ops_log = "";
}
void apply_op(char op) {
if (ops_count >= T_CONST) return;
bool valid = true;
if (op == 'U') { if (r > 0) r--; else valid = false; }
else if (op == 'D') { if (r < N_CONST - 1) r++; else valid = false; }
else if (op == 'L') { if (c > 0) c--; else valid = false; }
else if (op == 'R') { if (c < N_CONST - 1) c++; else valid = false; }
else if (op == 'W') { grid[r][c] ^= s; }
else if (op == 'C') { s ^= grid[r][c]; }
else { valid = false; }
if (valid) { ops_count++; ops_log += op; }
}
void apply_ops_string(const string& ops) {
for (char op : ops) { apply_op(op); }
}
long long calculate_total_score() const {
long long total_score = 0;
for(const auto& row : grid) {
for(int cell_val : row) {
total_score += cell_val;
}
}
return total_score;
}
};
// --- ヘルパー関数 ---
string get_simple_move_ops(int r1, int c1, int r2, int c2) {
string path_ops = "";
string vert_move = (r1 < r2) ? "D" : "U";
string horz_move = (c1 < c2) ? "R" : "L";
for (int i = 0; i < abs(r1 - r2); ++i) path_ops += vert_move;
for (int i = 0; i < abs(c1 - c2); ++i) path_ops += horz_move;
return path_ops;
}
/**
* @brief 特定のターゲット(tr, tc)への最適な操作列を見つける（修正版）
* @param current_state 現在の状態
* @param tr ターゲットの行
* @param tc ターゲットの列
* @return pair<string, long long> {操作列, スコア増加量}
* @note コピー('C')操作は、目的地での書き込みスコアが上がる場合のみ行う貪欲戦略に変更。
* それに伴い、乱択試行ループは不要になったため削除。
*/
pair<string, long long> find_best_ops_for_target(const State& current_state, int tr, int tc) {
string move_ops = get_simple_move_ops(current_state.r, current_state.c, tr, tc);
string total_ops = "";
long long total_increase = 0;
// このターゲットへの移動・操作をシミュレーションするための一次的な状態
int temp_s = current_state.s;
vector<vector<int>> temp_grid = current_state.grid;
int temp_r = current_state.r;
int temp_c = current_state.c;
// --- 経路上での操作シミュレーション ---
for (char op : move_ops) {
// 残り操作回数チェック
if (current_state.ops_count + total_ops.length() >= T_CONST) break;
total_ops += op;
if (op == 'U') temp_r--; else if (op == 'D') temp_r++;
else if (op == 'L') temp_c--; else if (op == 'R') temp_c++;
// --- 経路上での貪欲な書き込み('W') ---
// 途中のマスでも、書き込むことでスコアが上がるなら書き込む
long long potential_w_increase = (long long)(temp_grid[temp_r][temp_c] ^ temp_s) - temp_grid[temp_r][temp_c];
int dist_to_target = abs(temp_r - tr) + abs(temp_c - tc);
// 書き込み(1)と目的地までの移動(dist)をしても操作回数が残るかチェック
if (potential_w_increase > 0 && current_state.ops_count + total_ops.length() + 1 + dist_to_target <= T_CONST) {
total_ops += 'W';
total_increase += potential_w_increase;
temp_grid[temp_r][temp_c] ^= temp_s;
}
// --- 経路上での貪欲なコピー('C') ---
// ★★★ 修正点 ★★★
// 乱択ではなく、目的地でのスコアが上がるかという貪欲な基準でコピーを判断
if (current_state.ops_count + total_ops.length() < T_CONST) {
int s_before_copy = temp_s;
int s_after_copy = temp_s ^ temp_grid[temp_r][temp_c];
int target_value = temp_grid[tr][tc]; // 経路上のWを反映したグリッドで評価
// コピーした場合としなかった場合で、目的地でのスコアを比較
long long score_at_target_if_no_copy = (long long)(target_value ^ s_before_copy);
long long score_at_target_if_copy = (long long)(target_value ^ s_after_copy);
if (score_at_target_if_copy > score_at_target_if_no_copy) {
total_ops += 'C';
temp_s = s_after_copy; // シミュレーションのsを更新
}
}
}
// --- 目的地での最終的な書き込み('W') ---
if (current_state.ops_count + total_ops.length() < T_CONST) {
long long final_increase = (long long)(temp_grid[tr][tc] ^ temp_s) - temp_grid[tr][tc];
if (final_increase > 0) {
total_ops += 'W';
total_increase += final_increase;
}
}
if (total_increase > 0) {
return {total_ops, total_increase};
} else {
// スコア改善が見込めない場合は、移動だけを行う
return {move_ops, -1};
}
}
/**
* @brief 指定された訪問順で完全なシミュレーションを実行し、最終状態を返す
* @param visit_order 訪問するマスの順序
* @param initial_grid 初期盤面
* @return State シミュレーション後の最終状態
*/
State run_simulation(vector<pair<int, int>> visit_order, const vector<vector<int>>& initial_grid) {
State current_state(initial_grid);
vector<pair<int, int>> postponed_queue;
// 序盤フェーズ
int targets_visited = 0;
while (targets_visited < INITIAL_PHASE_TARGETS && !visit_order.empty()) {
if (current_state.ops_count >= T_CONST) break;
pair<int, int> target_pos = visit_order.front();
int dist = abs(current_state.r - target_pos.first) + abs(current_state.c - target_pos.second);
if (dist > MAX_DIST_INITIAL_PHASE) {
postponed_queue.push_back(target_pos);
visit_order.erase(visit_order.begin());
continue;
}
pair<string, long long> result = find_best_ops_for_target(current_state, target_pos.first, target_pos.second);
current_state.apply_ops_string(result.first);
visit_order.erase(visit_order.begin());
targets_visited++;
}
// 中盤フェーズ
visit_order.insert(visit_order.end(), postponed_queue.begin(), postponed_queue.end());
while (!visit_order.empty()) {
if (current_state.ops_count >= T_CONST) break;
pair<int, int> target_pos = visit_order.front();
pair<string, long long> result = find_best_ops_for_target(current_state, target_pos.first, target_pos.second);
current_state.apply_ops_string(result.first);
visit_order.erase(visit_order.begin());
}
// 後半戦略
while (true) {
int remaining_ops = T_CONST - current_state.ops_count;
if (remaining_ops < 2) break;
int best_target_r = -1, best_target_c = -1;
int min_score = -1;
for (int r = 0; r < N_CONST; ++r) {
for (int c = 0; c < N_CONST; ++c) {
int dist = abs(current_state.r - r) + abs(current_state.c - c);
if (dist == 0 || dist >= remaining_ops) continue;
bool is_target_candidate = false;
if (remaining_ops > MIN_DIST_FOR_TARGETING + dist + 5) {
if (dist >= MIN_DIST_FOR_TARGETING) is_target_candidate = true;
} else { is_target_candidate = true; }
if (is_target_candidate) {
if (best_target_r == -1 || current_state.grid[r][c] < min_score) {
min_score = current_state.grid[r][c];
best_target_r = r; best_target_c = c;
}
}
}
}
if (best_target_r == -1) break;
pair<string, long long> result = find_best_ops_for_target(current_state, best_target_r, best_target_c);
current_state.apply_ops_string(result.first);
}
return current_state;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto start_time = chrono::steady_clock::now();
int N_in, T_in;
cin >> N_in >> T_in;
vector<vector<int>> initial_grid(N_CONST, vector<int>(N_CONST));
for (int i = 0; i < N_CONST; ++i) {
for (int j = 0; j < N_CONST; ++j) {
cin >> initial_grid[i][j];
}
}
// --- 焼きなまし法の初期化 ---
vector<pair<int, int>> base_order;
for (int i = 0; i < N_CONST; ++i) {
for (int j = 0; j < N_CONST; ++j) {
if (i == 0 && j == 0) continue;
base_order.push_back({i, j});
}
}
shuffle(base_order.begin(), base_order.end(), rng);
vector<pair<int, int>> current_order = base_order;
State current_sim_state = run_simulation(current_order, initial_grid);
State best_state = current_sim_state; // ★ 最良の状態を保存
long long current_score = current_sim_state.calculate_total_score();
long long best_score = current_score;
int iteration = 0;
int accepted_count = 0;
cerr << "[SA] Initial Score: " << best_score << endl;
// --- 焼きなましループ ---
while(true) {
auto current_time = chrono::steady_clock::now();
double elapsed_ms = chrono::duration_cast<chrono::milliseconds>(current_time - start_time).count();
if (elapsed_ms > TIME_LIMIT_MS) break;
iteration++;
vector<pair<int, int>> new_order = current_order;
// 近傍操作 (2-opt or 2-swap)
if (uniform_int_distribution<int>(0, 1)(rng) == 0) { // 2-opt
int i = uniform_int_distribution<int>(0, new_order.size() - 1)(rng);
int j = uniform_int_distribution<int>(0, new_order.size() - 1)(rng);
if (i > j) swap(i, j);
if (i != j) reverse(new_order.begin() + i, new_order.begin() + j);
} else { // 2-swap
int i = uniform_int_distribution<int>(0, new_order.size() - 1)(rng);
int j = uniform_int_distribution<int>(0, new_order.size() - 1)(rng);
if (i != j) swap(new_order[i], new_order[j]);
}
State new_state = run_simulation(new_order, initial_grid);
long long new_score = new_state.calculate_total_score();
double temp = SA_START_TEMP + (SA_END_TEMP - SA_START_TEMP) * elapsed_ms / TIME_LIMIT_MS;
double delta = new_score - current_score;
if (delta > 0 || (temp > 0 && uniform_real_distribution<double>(0.0, 1.0)(rng) < exp(delta / temp))) {
current_order = new_order;
current_score = new_score;
current_sim_state = new_state; // 現在の状態も更新
accepted_count++;
if (current_score > best_score) {
best_score = current_score;
best_state = current_sim_state; // ★ スコアが改善したら、状態を丸ごと保存
}
}
if (iteration % 100 == 0) {
cerr << "[SA] iter:" << iteration << " time:" << (int)elapsed_ms << "ms"
<< " temp:" << (int)temp << " score:" << current_score
<< " best:" << best_score << " accept_rate:" << (double)accepted_count/iteration << endl;
}
}
// --- 最良解の操作ログを生成して出力 ---
// ★ 保存しておいたベストな状態から直接ログを出力する
for (char op : best_state.ops_log) {
cout << op << "\n";
}
// --- 最終デバッグ出力 ---
cerr << "--- Final Debug Info ---" << endl;
cerr << "SA iterations: " << iteration << endl;
cerr << "Best score found: " << best_score << endl;
cerr << "Final operations count: " << best_state.ops_log.length() << "/" << T_CONST << endl;
// ★ 検算のため、最終出力のスコアも計算して表示
cerr << "Score from final output: " << best_state.calculate_total_score() << endl;
return 0;
}