結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ymym_tymblack
|
| 提出日時 | 2025-07-26 17:03:33 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,984 ms / 2,000 ms |
| コード長 | 17,034 bytes |
| コンパイル時間 | 5,018 ms |
| コンパイル使用メモリ | 328,516 KB |
| 実行使用メモリ | 8,528 KB |
| スコア | 5,053,468,044 |
| 最終ジャッジ日時 | 2025-07-26 17:07:22 |
| 合計ジャッジ時間 | 108,129 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const long long INF = 1LL << 60; // 十分大きな値 (ここでは 2^60 とする)
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string_view>
#include <type_traits>
template<class T> void chmin(T& a, T b) {
if (a > b) {
a = b;
}
}
template<class T> void chmax(T& a, T b) {
if (a < b) {
a = b;
}
}
#ifdef LOCAL
# include <debug_print.hpp>
# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
# define debug(...) (static_cast<void>(0))
#endif
int N, T;
vector<vector<int>> A;
int x = 0, y = 0, s = 0;
vector<string> command_list = {"U", "D", "L", "R", "W", "C"};
// 移動可能かどうかを判定
bool can_move(int x, int y, const string& command) {
if (command == "U") {
return x > 0;
} else if (command == "D") {
return x < N - 1;
} else if (command == "L") {
return y > 0;
} else if (command == "R") {
return y < N - 1;
}
return true;
}
// コマンドを実行
void process_command(vector<vector<int>>& board, int& x, int& y, int& s, const string& command) {
if (command == "U") {
x = x - 1;
} else if (command == "D") {
x = x + 1;
} else if (command == "L") {
y = y - 1;
} else if (command == "R") {
y = y + 1;
} else if (command == "W") {
board[x][y] ^= s;
} else if (command == "C") {
s ^= board[x][y];
}
}
// スコアを計算
int calc_score(const vector<vector<int>>& board) {
int score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
score += board[i][j];
}
}
return score;
}
// 改良された評価関数：現在のスコア + 潜在価値
long long enhanced_score(const vector<vector<int>>& board, int x, int y, int s, int remaining_moves, const vector<vector<int>>& initial_board) {
long long current_score = calc_score(board);
// 潜在価値の計算
long long potential = 0;
// アイデア1: sの状態評価
if (s == 0) {
potential -= 5000; // Cが無意味な状況を避けるペナルティ
} else {
potential += __builtin_popcount(s) * 100; // sが強い(多くのビットが立っている)状態を評価
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int dist = abs(i - x) + abs(j - y);
if (dist < remaining_moves) {
// アイデア2: 未訪問(未変更)セルへのボーナス
if (board[i][j] == initial_board[i][j]) {
potential += 1000 / (1 + dist);
}
// Write操作での期待上昇値
int after_write = board[i][j] ^ s;
if (after_write > board[i][j]) {
potential += (after_write - board[i][j]) / (1 + dist * 0.1);
}
// Copy操作での期待上昇値
int new_s = s ^ board[i][j];
if (__builtin_popcount(new_s) > __builtin_popcount(s)) {
potential += __builtin_popcount(new_s) * 10;
}
}
}
}
return current_score + potential * 0.3; // 潜在価値の重み調整
}
// 盤面の初期値を保持（焼きなまし時のリセット用）
// vector<vector<int>> initial_board; // グローバルからは削除し、mainで管理
// 時間計測用
inline long long now() {
return chrono::duration_cast<chrono::milliseconds>(
chrono::steady_clock::now().time_since_epoch())
.count();
}
// 与えられた手列をシミュレートし，スコアを返す。
// 無効な手列なら false を返す。
bool simulate(const vector<string>& seq, long long& score_out, const vector<vector<int>>& initial_board) {
vector<vector<int>> board = initial_board; // コピー
int tx = 0, ty = 0, ts = 0;
for (const string& cmd : seq) {
if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") &&
!can_move(tx, ty, cmd)) {
return false; // 壁に衝突
}
process_command(board, tx, ty, ts, cmd);
}
score_out = calc_score(board);
return true;
}
// Greedy で初期手列を構築（改良版：2手先読み）
vector<string> build_greedy_sequence(int T, const vector<vector<int>>& initial_board) {
vector<string> seq;
seq.reserve(T);
vector<vector<int>> board = initial_board;
int cx = 0, cy = 0, cs = 0;
random_device rd;
mt19937 rng(rd());
for (int step = 0; step < T; ++step) {
long long best_score = LLONG_MIN;
string best_cmd = "W";
// 2手先まで読む改良版貪欲
for (const string& cmd1 : command_list) {
if ((cmd1 == "U" || cmd1 == "D" || cmd1 == "L" || cmd1 == "R") && !can_move(cx, cy, cmd1)) continue;
// 1手目を試す
int nx1 = cx, ny1 = cy, ns1 = cs;
vector<vector<int>> tmp1 = board;
process_command(tmp1, nx1, ny1, ns1, cmd1);
long long score1 = enhanced_score(tmp1, nx1, ny1, ns1, T - step - 1, initial_board);
// 2手先も見る（時間に余裕があるとき）
if (step < T - 1) {
long long best_score2 = score1;
for (const string& cmd2 : command_list) {
if ((cmd2 == "U" || cmd2 == "D" || cmd2 == "L" || cmd2 == "R") && !can_move(nx1, ny1, cmd2)) continue;
int nx2 = nx1, ny2 = ny1, ns2 = ns1;
vector<vector<int>> tmp2 = tmp1;
process_command(tmp2, nx2, ny2, ns2, cmd2);
long long score2 = enhanced_score(tmp2, nx2, ny2, ns2, T - step - 2, initial_board);
if (score2 > best_score2) {
best_score2 = score2;
}
}
score1 = best_score2 * 0.7 + score1 * 0.3; // 2手先と1手先の重み付き平均
}
if (score1 > best_score) {
best_score = score1;
best_cmd = cmd1;
}
}
// ランダム要素も少し混ぜる
if (rng() % 10 == 0) {
vector<string> cand;
for (const string& cmd : command_list) {
if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R")) {
if (can_move(cx, cy, cmd)) cand.push_back(cmd);
} else {
cand.push_back(cmd);
}
}
uniform_int_distribution<int> uni(0, (int)cand.size() - 1);
best_cmd = cand[uni(rng)];
}
process_command(board, cx, cy, cs, best_cmd);
seq.push_back(best_cmd);
}
return seq;
}
// 任意の状態から貪欲に hand_count 手の手列を生成 (盤面と状態を更新)
vector<string> greedy_from_state(vector<vector<int>>& board, int& cx, int& cy, int& cs, int hand_count, mt19937& rng, const vector<vector<int>>& initial_board) {
vector<string> seq;
seq.reserve(hand_count);
uniform_int_distribution<int> uni_dir(0, 5);
for (int step = 0; step < hand_count; ++step) {
long long best_score = LLONG_MIN;
string best_cmd = command_list[uni_dir(rng)]; // fallback
long long base_score = calc_score(board);
for (const string& cmd : command_list) {
if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") && !can_move(cx, cy, cmd)) continue;
int nx = cx, ny = cy, ns = cs;
vector<vector<int>> tmp = board;
process_command(tmp, nx, ny, ns, cmd);
long long sc = enhanced_score(tmp, nx, ny, ns, hand_count - step - 1, initial_board);
if (sc > best_score) {
best_score = sc;
best_cmd = cmd;
}
}
if (best_score <= base_score) {
// たまにランダムで揺らす
best_cmd = command_list[uni_dir(rng)];
while ((best_cmd == "U" || best_cmd == "D" || best_cmd == "L" || best_cmd == "R") && !can_move(cx, cy, best_cmd)) {
best_cmd = command_list[uni_dir(rng)];
}
}
process_command(board, cx, cy, cs, best_cmd);
seq.push_back(best_cmd);
}
return seq;
}
// ビームサーチで hand_count 手の手列を構築
vector<string> beam_search_from_state(const vector<vector<int>>& init_board_arg, int x0, int y0, int s0, int hand_count, const vector<vector<int>>& initial_board, int beam_width = 200) {
struct Node {
vector<vector<int>> board;
int x, y, s;
long long score;
vector<string> path;
bool operator<(const Node& other) const { // for priority_queue (min-heap)
return score > other.score; // 逆順（高スコア優先）
}
};
vector<Node> beam;
beam.reserve(beam_width);
beam.push_back({init_board_arg, x0, y0, s0, enhanced_score(init_board_arg, x0, y0, s0, hand_count, initial_board), {}});
for (int depth = 0; depth < hand_count; ++depth) {
vector<Node> cand;
cand.reserve(beam.size() * 6);
for (const Node& node : beam) {
for (const string& cmd : command_list) {
if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") && !can_move(node.x, node.y, cmd)) continue;
Node nxt = node; // コピー
nxt.path.push_back(cmd);
process_command(nxt.board, nxt.x, nxt.y, nxt.s, cmd);
nxt.score = enhanced_score(nxt.board, nxt.x, nxt.y, nxt.s, hand_count - depth - 1, initial_board);
cand.push_back(move(nxt));
}
}
// 上位 beam_width を残す
nth_element(cand.begin(), cand.begin() + min(beam_width, (int)cand.size()) - 1, cand.end());
cand.resize(min(beam_width, (int)cand.size()));
beam.swap(cand);
}
// 最良ノードを取得
Node* best = &beam[0];
for (Node& n : beam) if (n.score > best->score) best = &n;
return best->path;
}
// 焼きなましで手列を改善
vector<string> simulated_annealing(vector<string> seq, long long best_score, const vector<vector<int>>& initial_board, long long time_limit_ms = 1800) {
const long long start_time = now();
const double T0 = 2000.0;
const double T_end = 1e-3;
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> cmd_dist(0, (int)command_list.size() - 1);
vector<string> best_seq = seq;
long long iter = 0;
while (now() - start_time < time_limit_ms) {
++iter;
double progress = (double)(now() - start_time) / (double)time_limit_ms;
double temperature = pow(T_end / T0, progress) * T0;
vector<string> new_seq = seq;
long long new_score;
// --- 近傍生成: 3種類の戦略 ---
int r = rng() % 100; // より細かい確率制御
if (r == 0 && now() - start_time < time_limit_ms - 600) { // 1% でビームサーチ (十分な時間がある場合)
uniform_int_distribution<int> pos_dist(0, T - 2);
int l = pos_dist(rng);
int depth = min(T - l, 40); // 深さを少し増加
int width = 50; // ビーム幅も増加
// l までシミュレートして状態取得
vector<vector<int>> board = initial_board;
int cx = 0, cy = 0, cs = 0;
bool is_valid = true;
for (int i = 0; i < l; ++i) {
if (!can_move(cx, cy, seq[i]) && (seq[i] == "U" || seq[i] == "D" || seq[i] == "L" || seq[i] == "R")) {
is_valid = false;
break;
}
process_command(board, cx, cy, cs, seq[i]);
}
if (is_valid) {
vector<string> rebuilt = beam_search_from_state(board, cx, cy, cs, depth, initial_board);
for (int i = 0; i < rebuilt.size(); ++i) new_seq[l + i] = rebuilt[i];
}
} else if (r < 8) { // 7% で大規模再構築 (greedy) - 頻度を下げる
uniform_int_distribution<int> pos_dist(0, T - 2);
int l = pos_dist(rng);
int len = min(T - l, (int)(T / 5)); // 全体の 20% 程度を再構築
// l までシミュレートして状態取得
vector<vector<int>> board = initial_board;
int cx = 0, cy = 0, cs = 0;
for (int i = 0; i < l; ++i) {
if (!can_move(cx, cy, seq[i]) && (seq[i] == "U" || seq[i] == "D" || seq[i] == "L" || seq[i] == "R")) {
// 現在の手列がそもそも無効なら break
board.clear();
break;
}
process_command(board, cx, cy, cs, seq[i]);
}
if (!board.empty()) {
// 再構築部分を greedy で生成
vector<string> rebuilt = greedy_from_state(board, cx, cy, cs, len, rng, initial_board);
for (int i = 0; i < len; ++i) new_seq[l + i] = rebuilt[i];
}
} else { // 92% で小規模変形 - 細かい調整を重視
// 小規模（従来）のランダム区間書き換え
uniform_int_distribution<int> pos_dist(0, T - 1);
int l = pos_dist(rng);
int len = min(T - l, (int)(pos_dist(rng) % 8 + 1)); // 長さを少し短く
uniform_int_distribution<int> cmd_dist_local(0, (int)command_list.size() - 1);
for (int i = l; i < l + len; ++i) {
new_seq[i] = command_list[cmd_dist_local(rng)];
}
}
if (!simulate(new_seq, new_score, initial_board)) continue;
long long delta = new_score - best_score;
if (delta > 0 || exp((double)delta / temperature) > (double)rng() / rng.max()) {
seq.swap(new_seq);
best_score = new_score;
best_seq = seq;
// 改善時にログ出力（デバッグ用）
if (delta > 0) {
cerr << "Improvement at iter " << iter << ": " << best_score << " (++" << delta << ")" << endl;
}
}
}
cerr << "SA completed. Iterations: " << iter << ", Best score: " << best_score << endl;
return best_seq;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
const long long TOTAL_TIME_LIMIT = 1980; // 2秒の制限時間からマージンを引いた値
const long long main_start_time = now();
// 入力
cin >> N >> T;
A.resize(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
vector<vector<int>> initial_board = A;
// アイデア5: 複数回初期解を生成し、最良のものを選択
vector<string> best_initial_seq;
long long best_initial_score = -1;
int num_initial_solutions = 5;
cerr << "Generating " << num_initial_solutions << " initial solutions..." << endl;
for (int i = 0; i < num_initial_solutions; ++i) {
// 初期解生成に時間を使いすぎないようにタイムアウトを設定
if (now() - main_start_time > 500) {
cerr << "Timeout for initial solution generation. Breaking." << endl;
break;
}
vector<string> current_seq = build_greedy_sequence(T, initial_board);
long long current_score;
if (simulate(current_seq, current_score, initial_board)) {
if (current_score > best_initial_score) {
best_initial_score = current_score;
best_initial_seq = current_seq;
}
}
cerr << " Solution " << i + 1 << " score: " << current_score << endl;
}
cerr << "Best initial score: " << best_initial_score << endl;
// 焼きなましに割り当てる残り時間を計算
long long elapsed_time = now() - main_start_time;
long long sa_time_limit = TOTAL_TIME_LIMIT - elapsed_time;
vector<string> final_seq;
if (sa_time_limit > 100 && !best_initial_seq.empty()) { // SAに最低100msは確保
cerr << "Starting Simulated Annealing with time limit: " << sa_time_limit << "ms" << endl;
// 焼きなましで改善
final_seq = simulated_annealing(best_initial_seq, best_initial_score, initial_board, sa_time_limit);
} else {
cerr << "Not enough time for SA. Outputting best initial solution." << endl;
final_seq = best_initial_seq;
}
// 出力
if (!final_seq.empty()) {
for (const string& cmd : final_seq) {
cout << cmd << '\n';
}
}
return 0;
}