結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 ymym_tymblack
|
| 提出日時 | 2025-07-26 15:33:52 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,805 ms / 2,000 ms |
| コード長 | 6,633 bytes |
| コンパイル時間 | 3,779 ms |
| コンパイル使用メモリ | 306,496 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 4,409,129,460 |
| 最終ジャッジ日時 | 2025-07-26 15:35:31 |
| 合計ジャッジ時間 | 98,187 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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;
}
// 盤面の初期値を保持（焼きなまし時のリセット用）
vector<vector<int>> initial_board;
// 時間計測用
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) {
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 で初期手列を構築
vector<string> build_greedy_sequence(int T) {
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";
// 現在の盤面得点
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;
// 状態をコピーして 1 手だけ適用
int nx = cx, ny = cy, ns = cs;
vector<vector<int>> tmp_board = board;
process_command(tmp_board, nx, ny, ns, cmd);
long long sc = calc_score(tmp_board);
if (sc > best_score) {
best_score = sc;
best_cmd = cmd;
}
}
// すべての cmd が同点（動かすだけ）ならランダムで選ぶ
if (best_score <= base_score) {
// ランダムで動ける方向または C を選択
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); // W or C
}
}
uniform_int_distribution<int> uni(0, (int)cand.size() - 1);
best_cmd = cand[uni(rng)];
}
// best_cmd を実際に適用
process_command(board, cx, cy, cs, best_cmd);
seq.push_back(best_cmd);
}
return seq;
}
// 焼きなましで手列を改善
vector<string> simulated_annealing(vector<string> seq, long long best_score, 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;
// ランダム区間を書き換え (長さ 1～10)
uniform_int_distribution<int> pos_dist(0, T - 1);
int l = pos_dist(rng);
int len = min(T - l, (int)(pos_dist(rng) % 10 + 1));
vector<string> new_seq = seq;
for (int i = l; i < l + len; ++i) {
new_seq[i] = command_list[cmd_dist(rng)];
}
long long new_score;
if (!simulate(new_seq, new_score)) continue; // 無効手列
long long delta = new_score - best_score;
if (delta > 0 || exp(delta / temperature) > (double)rng() / rng.max()) {
// 受理
seq.swap(new_seq);
best_score = new_score;
if (best_score > calc_score(initial_board)) {
best_seq = seq;
}
}
}
return best_seq;
}
int main() {
// 入力
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];
}
}
// 初期盤面を保存
initial_board = A;
// Greedy で初期手列を生成
vector<string> seq = build_greedy_sequence(T);
long long best_score;
simulate(seq, best_score);
// 焼きなましで改善
seq = simulated_annealing(seq, best_score);
// 出力
for (const string& cmd : seq) {
cout << cmd << '\n';
}
return 0;
}