結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 mtmr_s1
|
| 提出日時 | 2025-07-26 18:04:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,988 ms / 2,000 ms |
| コード長 | 16,163 bytes |
| コンパイル時間 | 1,517 ms |
| コンパイル使用メモリ | 125,576 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,142,141,990 |
| 最終ジャッジ日時 | 2025-07-26 18:06:20 |
| 合計ジャッジ時間 | 104,989 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <random>
#include <cmath>
#include <cstdint>
#include <array>
using namespace std;
// --- パラメータ調整欄 ---
// --- 戦略パラメータ ---
const int NUM_PATHS_TO_TRY_LATE_GAME = 2; // 終盤で試す経路の数
// --- 焼きなましパラメータ ---
const double TIME_LIMIT_MS = 1985.0;
const double SA_START_TEMP = 100000.0;
const double SA_END_TEMP = 3.0;
const double TWO_OPT_PROBABILITY = 0.1;
const int TIME_CHECK_INTERVAL = 250;
// --- グローバル定数 (変更不要) ---
const int N_CONST = 10;
const int T_CONST = 1000;
// --- xoshiro256++ 高速乱数生成器 ---
// see: https://prng.di.unimi.it/
class Xoshiro256 {
public:
using result_type = uint64_t;
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return UINT64_MAX; }
Xoshiro256() : Xoshiro256(chrono::steady_clock::now().time_since_epoch().count()) {}
explicit Xoshiro256(uint64_t seed) {
s[0] = split_mix64(seed);
s[1] = split_mix64(seed);
s[2] = split_mix64(seed);
s[3] = split_mix64(seed);
}
result_type operator()() {
const uint64_t result = rotl(s[0] + s[3], 23) + s[0];
const uint64_t t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return result;
}
inline uint64_t next_int(uint64_t upper_bound) {
if (upper_bound == 0) return 0;
return operator()() % upper_bound;
}
inline double next_double() {
return (operator()() >> 11) * (1.0 / (1ULL << 53));
}
private:
array<uint64_t, 4> s;
static inline uint64_t rotl(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}
static uint64_t split_mix64(uint64_t& x) {
x += 0x9e3779b97f4a7c15;
uint64_t z = x;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
return z ^ (z >> 31);
}
};
// グローバル乱数生成器
Xoshiro256 rng;
// ★★★ 変更点: gridをvectorからarrayに変更 ★★★
using Grid = array<array<int, N_CONST>, N_CONST>;
/**
* @struct State
* @brief 現在のゲームの状態を管理する構造体
*/
struct State {
int r, c;
int s;
Grid grid;
int ops_count;
string ops_log;
long long score;
State(const Grid& initial_grid) {
r = 0; c = 0; s = 0;
grid = initial_grid;
ops_count = 0;
ops_log.reserve(T_CONST + 50);
score = 0;
for(const auto& row : grid) {
for(int cell_val : row) {
score += cell_val;
}
}
}
// ★★★ 変更点: 文字列操作をpush_backに ★★★
inline 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') {
long long old_val = grid[r][c];
grid[r][c] ^= s;
score += (long long)grid[r][c] - old_val;
}
else if (op == 'C') { s ^= grid[r][c]; }
else { valid = false; }
if (valid) {
ops_count++;
ops_log.push_back(op);
}
}
inline void apply_ops_string(const string& ops) {
for (char op : ops) {
apply_op(op);
}
}
};
// --- ヘルパー関数 ---
// ★★★ 変更点: 文字列操作をappendに、inline化 ★★★
inline string get_simple_move_ops(int r1, int c1, int r2, int c2) {
string path_ops;
int dr = abs(r1 - r2);
int dc = abs(c1 - c2);
path_ops.reserve(dr + dc);
if (r1 < r2) path_ops.append(dr, 'D'); else path_ops.append(dr, 'U');
if (c1 < c2) path_ops.append(dc, 'R'); else path_ops.append(dc, 'L');
return path_ops;
}
/**
* @brief 指定された経路を通った場合の最適な操作列とスコア上昇量を計算する
*/
inline pair<string, long long> find_best_ops_for_path(const State& current_state, const string& move_ops, int tr, int tc) {
string total_ops;
total_ops.reserve(move_ops.length() * 2); // 事前に多めに確保
long long total_increase = 0;
int temp_s = current_state.s;
Grid temp_grid = current_state.grid; // arrayのコピーは高速
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.push_back(op);
if (op == 'U') temp_r--; else if (op == 'D') temp_r++;
else if (op == 'L') temp_c--; else if (op == 'R') temp_c++;
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);
if (potential_w_increase > 0 && current_state.ops_count + total_ops.length() + 1 + dist_to_target <= T_CONST) {
total_ops.push_back('W');
total_increase += potential_w_increase;
temp_grid[temp_r][temp_c] ^= temp_s;
}
if (current_state.ops_count + total_ops.length() < T_CONST) {
int s_after_copy = temp_s ^ temp_grid[temp_r][temp_c];
long long score_at_target_if_no_copy = (long long)(current_state.grid[tr][tc] ^ temp_s);
long long score_at_target_if_copy = (long long)(current_state.grid[tr][tc] ^ s_after_copy);
if (score_at_target_if_copy > score_at_target_if_no_copy) {
total_ops.push_back('C');
temp_s = s_after_copy;
}
}
}
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.push_back('W');
total_increase += final_increase;
}
}
return {total_ops, total_increase};
}
/**
* @brief 特定のターゲット(tr, tc)への最適な操作列を見つける（序盤・中盤用）
*/
inline 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);
return find_best_ops_for_path(current_state, move_ops, tr, tc);
}
/**
* @brief スタートからゴールまでのランダムな経路を生成する
*/
inline vector<string> generate_random_paths(int r1, int c1, int r2, int c2, int count) {
vector<string> paths;
string base_moves;
int dr = abs(r1 - r2);
int dc = abs(c1 - c2);
base_moves.reserve(dr + dc);
if (r1 < r2) base_moves.append(dr, 'D'); else base_moves.append(dr, 'U');
if (c1 < c2) base_moves.append(dc, 'R'); else base_moves.append(dc, 'L');
paths.push_back(base_moves);
// シャッフルして多様な経路を生成
for (int i = 0; i < count - 1; ++i) {
shuffle(base_moves.begin(), base_moves.end(), rng);
if (find(paths.begin(), paths.end(), base_moves) == paths.end()) {
paths.push_back(base_moves);
}
}
return paths;
}
/**
* @brief 指定された訪問順で完全なシミュレーションを実行し、最終状態を返す
*/
State run_simulation(const vector<pair<int, int>>& visit_order, const Grid& initial_grid) {
State current_state(initial_grid);
// 序盤・中盤フェーズ: 貪欲にターゲットを巡る
for(const auto& target_pos : visit_order) {
if (current_state.ops_count >= T_CONST) break;
auto result = find_best_ops_for_target(current_state, target_pos.first, target_pos.second);
current_state.apply_ops_string(result.first);
}
// 後半戦略 (改善版)
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;
double max_gain_per_op = 0.0;
// 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 + 1 > remaining_ops) continue;
long long gain = (long long)(current_state.grid[r][c] ^ current_state.s) - current_state.grid[r][c];
if (gain <= 0) continue;
double gain_per_op = (double)gain / (dist + 1.0);
if (gain_per_op > max_gain_per_op) {
max_gain_per_op = gain_per_op;
best_target_r = r;
best_target_c = c;
}
}
}
if (best_target_r == -1) break; // 利益の出るターゲットが見つからない
// 2. そのターゲットへの複数の経路を試し、最善手を探す
vector<string> candidate_paths = generate_random_paths(current_state.r, current_state.c, best_target_r, best_target_c, NUM_PATHS_TO_TRY_LATE_GAME);
string best_overall_ops = "";
long long max_overall_gain = -1;
for (const auto& path : candidate_paths) {
pair<string, long long> result = find_best_ops_for_path(current_state, path, best_target_r, best_target_c);
if (result.second > max_overall_gain) {
if (current_state.ops_count + result.first.length() <= T_CONST) {
max_overall_gain = result.second;
best_overall_ops = result.first;
}
}
}
// 3. 見つかった最善手があれば適用する
if (max_overall_gain > 0) {
current_state.apply_ops_string(best_overall_ops);
} else {
break; // どの経路でも利益が出なければ終了
}
}
return current_state;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto total_start_time = chrono::steady_clock::now();
int N_in, T_in;
cin >> N_in >> T_in;
Grid initial_grid; // ★★★ 変更点: vectorからarrayに
for (int i = 0; i < N_CONST; ++i) {
for (int j = 0; j < N_CONST; ++j) {
cin >> initial_grid[i][j];
}
}
// 多点スタートのメインループ
const int NUM_STARTS = 2;
State overall_best_state(initial_grid);
overall_best_state.score = -1; // 負のスコアで初期化
for (int run_idx = 0; run_idx < NUM_STARTS; ++run_idx) {
// --- 時間管理 ---
double total_elapsed_ms_before_run = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - total_start_time).count();
if (total_elapsed_ms_before_run >= TIME_LIMIT_MS) {
break;
}
cerr << "\n--- Multi-Start Run " << run_idx + 1 << "/" << NUM_STARTS << " ---" << endl;
auto run_start_time = chrono::steady_clock::now();
// 残り時間を残りの実行回数で均等に分割
double time_limit_for_this_run = (TIME_LIMIT_MS - total_elapsed_ms_before_run);
if (run_idx < NUM_STARTS - 1) {
time_limit_for_this_run /= (NUM_STARTS - run_idx);
}
// --- この回の実行のための初期解を生成 ---
vector<pair<int, int>> base_order;
base_order.reserve(N_CONST * N_CONST - 1);
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_run_best_state = run_simulation(current_order, initial_grid);
long long current_run_best_score = current_run_best_state.score;
long long current_score = current_run_best_score;
int iteration = 0;
int accepted_count = 0;
cerr << "[SA Run " << run_idx + 1 << "] Initial Score: " << current_run_best_score << endl;
// --- この回の実行のための焼きなましループ ---
while(true) {
iteration++;
double run_elapsed_ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - run_start_time).count();
if (run_elapsed_ms >= time_limit_for_this_run) break;
double total_elapsed_ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - total_start_time).count();
if (total_elapsed_ms >= TIME_LIMIT_MS) break;
// --- 近傍解の生成 ---
vector<pair<int, int>> new_order = current_order;
if (rng.next_double() < TWO_OPT_PROBABILITY) {
int i = rng.next_int(new_order.size());
int j = rng.next_int(new_order.size());
if (i == j) continue;
if (i > j) swap(i, j);
reverse(new_order.begin() + i, new_order.begin() + j);
} else {
int i = rng.next_int(new_order.size());
int j = rng.next_int(new_order.size());
if (i == j) continue;
swap(new_order[i], new_order[j]);
}
// --- 解の評価と遷移判定 ---
State new_state = run_simulation(new_order, initial_grid);
long long new_score = new_state.score;
// 温度は「この回の実行」の時間でスケジュール
double temp = SA_START_TEMP + (SA_END_TEMP - SA_START_TEMP) * run_elapsed_ms / time_limit_for_this_run;
double delta = (double)new_score - current_score;
if (delta > 0 || (temp > 0 && rng.next_double() < exp(delta / temp))) {
current_order = move(new_order);
current_score = new_score;
accepted_count++;
if (current_score > current_run_best_score) {
current_run_best_score = current_score;
current_run_best_state = move(new_state);
}
}
if (iteration % TIME_CHECK_INTERVAL == 0) {
cerr << "[SA Run " << run_idx + 1 << "] iter:" << iteration << " time:" << (int)run_elapsed_ms << "ms"
<< " temp:" << (int)temp << " score:" << current_score
<< " best_in_run:" << current_run_best_score << " accept_rate:" << (iteration > 0 ? (double)accepted_count/iteration : 0.0) << endl;
}
}
// --- この回の実行結果を全体の最良解と比較・更新 ---
if (current_run_best_state.score > overall_best_state.score) {
cerr << "!!! New Overall Best Score: " << current_run_best_state.score << " (from run " << run_idx + 1 << ")" << endl;
overall_best_state = move(current_run_best_state);
}
}
// --- 全体で最良だった解を出力 ---
for (char op : overall_best_state.ops_log) {
cout << op << "\n";
}
cerr << "\n--- Final Debug Info ---" << endl;
cerr << "Multi-start runs attempted: " << NUM_STARTS << endl;
cerr << "Best score found: " << overall_best_state.score << endl;
cerr << "Final operations count: " << overall_best_state.ops_log.length() << "/" << T_CONST << endl;
State final_check_state(initial_grid);
final_check_state.apply_ops_string(overall_best_state.ops_log);
cerr << "Score from final output (re-calculated): " << final_check_state.score << endl;
return 0;
}