結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2025-07-29 02:39:10 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,084 ms / 2,000 ms |
| コード長 | 22,946 bytes |
| コンパイル時間 | 3,549 ms |
| コンパイル使用メモリ | 220,304 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 4,820,285,792 |
| 最終ジャッジ日時 | 2025-07-29 02:40:12 |
| 合計ジャッジ時間 | 60,783 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <climits>
#include <cassert>
#include <cstring>
using namespace std;
int N, T;
vector<vector<int>> A;
constexpr int MAX_BITS = 20;
constexpr double TIME_LIMIT = 1.8;
// ===== Phase 1: main7.cppの手順で上2桁を1で揃える =====
void input() {
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];
}
}
}
inline bool hasBit(int value, int bit_pos) {
return (value >> bit_pos) & 1;
}
int countMissingBits(const vector<vector<int>>& grid, int bit_pos) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!hasBit(grid[i][j], bit_pos)) {
count++;
}
}
}
return count;
}
// Phase 1: main7.cppと同じビット単位充填戦略（bit 19, 18のみ）
struct Phase1Result {
vector<char> operations;
pair<int, int> end_position;
vector<vector<int>> grid_state;
int s_value;
long long score;
};
Phase1Result phase1_bitWiseFill() {
auto start_time = chrono::high_resolution_clock::now();
vector<char> operations;
operations.reserve(T);
cerr << "=== Phase 1: Bit-wise Fill Strategy ===" << endl;
// 蛇行ルートを事前計算
vector<pair<int, int>> route;
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
for (int j = 0; j < N; j++) {
route.push_back({i, j});
}
} else {
for (int j = N - 1; j >= 0; j--) {
route.push_back({i, j});
}
}
}
int currentR = 0, currentC = 0;
int s = 0;
// 高位ビット（bit 19, 18）のみ処理
for (int bit = MAX_BITS - 1; bit >= 18; bit--) {
// 最初のビット（bit 19）の場合、sを初期化
if (bit == MAX_BITS - 1 && s == 0) {
bool initialized = false;
for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
int r = route[idx].first;
int c = route[idx].second;
if (hasBit(A[r][c], bit)) {
// このマスに移動
while ((currentR != r || currentC != c) && operations.size() < T) {
if (currentR < r) {
operations.push_back('D');
currentR++;
} else if (currentR > r) {
operations.push_back('U');
currentR--;
} else if (currentC < c) {
operations.push_back('R');
currentC++;
} else {
operations.push_back('L');
currentC--;
}
}
if (operations.size() >= T) break;
operations.push_back('C');
s ^= A[r][c];
initialized = true;
break;
}
}
if (!initialized) continue;
}
auto current_time = chrono::high_resolution_clock::now();
double elapsed = chrono::duration<double>(current_time - start_time).count();
if (elapsed >= TIME_LIMIT * 0.4) { // Phase1は40%の時間を使用
cerr << "Phase 1 time limit reached at bit " << bit << endl;
break;
}
if (operations.size() >= T - 200) { // Phase2用に200操作を残す
cerr << "Phase 1 operation limit reached at bit " << bit << endl;
break;
}
int missing_before = countMissingBits(A, bit);
if (missing_before == 0) continue;
cerr << "Processing bit " << bit << " (" << missing_before << " cells missing)" << endl;
// XOR戦略で上位ビットをクリア
for (int upper_bit = MAX_BITS - 1; upper_bit > bit; upper_bit--) {
if (hasBit(s, upper_bit) && operations.size() < T - 150) {
bool found = false;
for (int idx = 0; idx < route.size() && operations.size() < T - 100; idx++) {
int r = route[idx].first;
int c = route[idx].second;
if (hasBit(A[r][c], upper_bit)) {
while ((currentR != r || currentC != c) && operations.size() < T) {
if (currentR < r) {
operations.push_back('D');
currentR++;
} else if (currentR > r) {
operations.push_back('U');
currentR--;
} else if (currentC < c) {
operations.push_back('R');
currentC++;
} else {
operations.push_back('L');
currentC--;
}
}
if (operations.size() >= T) break;
operations.push_back('C');
s ^= A[r][c];
found = true;
break;
}
}
if (!found) break;
}
}
// 目標ビットを設定
if (!hasBit(s, bit) && operations.size() < T - 100) {
bool found = false;
for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
int r = route[idx].first;
int c = route[idx].second;
if (hasBit(A[r][c], bit)) {
while ((currentR != r || currentC != c) && operations.size() < T) {
if (currentR < r) {
operations.push_back('D');
currentR++;
} else if (currentR > r) {
operations.push_back('U');
currentR--;
} else if (currentC < c) {
operations.push_back('R');
currentC++;
} else {
operations.push_back('L');
currentC--;
}
}
if (operations.size() >= T) break;
operations.push_back('C');
s ^= A[r][c];
found = true;
break;
}
}
if (!found) break;
}
// 各セルを巡回して書き込み
int filled_count = 0;
for (int idx = 0; idx < route.size() && operations.size() < T - 50; idx++) {
int r = route[idx].first;
int c = route[idx].second;
if (!hasBit(A[r][c], bit)) {
while ((currentR != r || currentC != c) && operations.size() < T) {
if (currentR < r) {
operations.push_back('D');
currentR++;
} else if (currentR > r) {
operations.push_back('U');
currentR--;
} else if (currentC < c) {
operations.push_back('R');
currentC++;
} else {
operations.push_back('L');
currentC--;
}
}
if (operations.size() >= T) break;
operations.push_back('W');
A[r][c] ^= s;
filled_count++;
}
}
int missing_after = countMissingBits(A, bit);
cerr << "Bit " << bit << " processed: " << missing_before << " -> " << missing_after << " missing" << endl;
}
long long phase1_score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
phase1_score += A[i][j];
}
}
cerr << "Phase 1 complete: " << operations.size() << " operations, score: " << phase1_score << endl;
// Phase1の結果をまとめて返す
Phase1Result result;
result.operations = operations;
result.end_position = {currentR, currentC};
result.grid_state = A; // Phase1完了後のグリッド状態
result.s_value = s; // Phase1完了後のs値
result.score = phase1_score;
return result;
}
// ===== Phase 2: 順序最適化連続巡回焼きなまし =====
// 高速乱数生成器
uint64_t xorshift_state;
inline uint64_t xorshift64() {
xorshift_state ^= xorshift_state << 13;
xorshift_state ^= xorshift_state >> 7;
xorshift_state ^= xorshift_state << 17;
return xorshift_state;
}
inline double fastRandom() {
return (xorshift64() & 0x7FFFFFFF) * (1.0 / 2147483648.0);
}
// 連続巡回ルート生成
vector<pair<int, int>> generateContinuousRoute() {
vector<pair<int, int>> route;
cerr << "=== Generating Continuous Circuit Route ===" << endl;
for (int circuit = 0; circuit < 10; circuit++) {
if (circuit == 0) {
// 最初の周回は通常の蛇行
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
for (int j = 0; j < N; j++) {
route.push_back({i, j});
}
} else {
for (int j = N - 1; j >= 0; j--) {
route.push_back({i, j});
}
}
}
cerr << "Circuit " << circuit << ": (0,0)→...→(9,0)" << endl;
} else {
if (circuit % 2 == 1) {
// 奇数周回: 下から上へ、右から左へ蛇行
for (int i = N-1; i >= 0; i--) {
if ((N-1-i) % 2 == 0) {
for (int j = N-1; j >= 0; j--) {
route.push_back({i, j});
}
} else {
for (int j = 0; j < N; j++) {
route.push_back({i, j});
}
}
}
cerr << "Circuit " << circuit << ": (9,0)→...→(0,9)" << endl;
} else {
// 偶数周回: 上から下へ、左から右へ蛇行
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
for (int j = 0; j < N; j++) {
route.push_back({i, j});
}
} else {
for (int j = N - 1; j >= 0; j--) {
route.push_back({i, j});
}
}
}
cerr << "Circuit " << circuit << ": (0,9)→...→(9,0)" << endl;
}
}
}
cerr << "Total route points: " << route.size() << " (" << route.size()/100 << " circuits)" << endl;
return route;
}
// 順序最適化アクション構造
constexpr int MAX_ROUTE_POINTS = 1000;
enum ActionOrder {
NONE = 0, // 何もしない
COPY_ONLY = 1, // コピーのみ
WRITE_ONLY = 2, // 書き込みのみ
COPY_THEN_WRITE = 3, // コピー→書き込み
WRITE_THEN_COPY = 4 // 書き込み→コピー
};
struct OrderOptimizedAction {
ActionOrder order;
OrderOptimizedAction() : order(NONE) {}
bool hasCopy() const {
return order == COPY_ONLY || order == COPY_THEN_WRITE || order == WRITE_THEN_COPY;
}
bool hasWrite() const {
return order == WRITE_ONLY || order == COPY_THEN_WRITE || order == WRITE_THEN_COPY;
}
bool copyFirst() const {
return order == COPY_THEN_WRITE;
}
bool writeFirst() const {
return order == WRITE_THEN_COPY;
}
};
struct OrderOptimizedSolution {
OrderOptimizedAction actions[MAX_ROUTE_POINTS];
long long score;
OrderOptimizedSolution() : score(0) {}
};
// Phase 2: 順序最適化連続巡回焼きなまし法
vector<char> phase2_orderOptimizedSimulatedAnnealing(const Phase1Result& phase1_result) {
auto start_time = chrono::high_resolution_clock::now();
int remaining_ops = T - phase1_result.operations.size();
cerr << "=== Phase 2: Order-Optimized Continuous Circuit SA ===" << endl;
cerr << "Remaining operations: " << remaining_ops << endl;
xorshift_state = chrono::high_resolution_clock::now().time_since_epoch().count();
// 連続巡回ルート生成
vector<pair<int, int>> route = generateContinuousRoute();
// 初期解生成（順序も考慮）
OrderOptimizedSolution current;
for (int i = 0; i < MAX_ROUTE_POINTS; i++) {
double rand_val = fastRandom();
if (rand_val < 0.15) {
current.actions[i].order = COPY_ONLY;
} else if (rand_val < 0.30) {
current.actions[i].order = WRITE_ONLY;
} else if (rand_val < 0.50) {
current.actions[i].order = COPY_THEN_WRITE;
} else if (rand_val < 0.70) {
current.actions[i].order = WRITE_THEN_COPY;
} else {
current.actions[i].order = NONE;
}
}
// Phase1の状態を使ってスコア計算（順序考慮）
auto calculateScore = [&](const OrderOptimizedSolution& sol) -> long long {
// Phase1の結果からスタート
A = phase1_result.grid_state;
int s = phase1_result.s_value;
int currentR = phase1_result.end_position.first;
int currentC = phase1_result.end_position.second;
int ops_used = 0;
// 連続巡回実行（順序最適化）
for (int i = 0; i < route.size() && ops_used < remaining_ops; i++) {
int targetR = route[i].first;
int targetC = route[i].second;
// 移動コスト計算
int move_ops = abs(currentR - targetR) + abs(currentC - targetC);
ops_used += move_ops;
currentR = targetR;
currentC = targetC;
if (ops_used >= remaining_ops) break;
// 順序最適化アクション実行
ActionOrder order = sol.actions[i].order;
if (order == COPY_ONLY && ops_used < remaining_ops) {
ops_used++;
s ^= A[currentR][currentC];
}
else if (order == WRITE_ONLY && ops_used < remaining_ops) {
ops_used++;
A[currentR][currentC] ^= s;
}
else if (order == COPY_THEN_WRITE && ops_used + 1 < remaining_ops) {
// コピー→書き込みの順序
ops_used++;
s ^= A[currentR][currentC];
ops_used++;
A[currentR][currentC] ^= s;
}
else if (order == WRITE_THEN_COPY && ops_used + 1 < remaining_ops) {
// 書き込み→コピーの順序
ops_used++;
A[currentR][currentC] ^= s;
ops_used++;
s ^= A[currentR][currentC];
}
// NONE の場合は何もしない
}
long long total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
total += A[i][j];
}
}
return total;
};
current.score = calculateScore(current);
OrderOptimizedSolution best = current;
int iter = 0;
int improvements = 0;
int order_changes = 0;
// 順序最適化統計
int action_stats[5] = {0}; // NONE, COPY_ONLY, WRITE_ONLY, COPY_THEN_WRITE, WRITE_THEN_COPY
// 最適化された焼きなまし法
while (true) {
auto current_time = chrono::high_resolution_clock::now();
double elapsed = chrono::duration<double>(current_time - start_time).count();
double total_elapsed = chrono::duration<double>(current_time - start_time).count();
if (total_elapsed >= TIME_LIMIT * 0.95) break;
double progress = elapsed / (TIME_LIMIT * 0.6);
if (progress >= 1.0) break;
// 最適化された温度設定
double temp = 120000.0 * exp(-6.0 * progress);
// 近傍生成（順序も含めて変更）
OrderOptimizedSolution neighbor = current;
int point = xorshift64() % MAX_ROUTE_POINTS;
// 順序を含む近傍生成
ActionOrder old_order = neighbor.actions[point].order;
ActionOrder new_order;
// ランダムに新しい順序を選択（現在と異なるもの）
do {
int rand_choice = xorshift64() % 5;
new_order = static_cast<ActionOrder>(rand_choice);
} while (new_order == old_order);
neighbor.actions[point].order = new_order;
neighbor.score = calculateScore(neighbor);
double delta = neighbor.score - current.score;
bool accept = false;
if (delta > 0) {
accept = true;
improvements++;
if (old_order != new_order) order_changes++;
} else if (temp > 0.1) {
accept = (fastRandom() < exp(delta / temp));
}
if (accept) {
current = neighbor;
if (current.score > best.score) {
best = current;
}
}
if (iter % 10000 == 0) {
cerr << "SA iter: " << iter << ", temp: " << temp << ", best: " << best.score << ", order_changes: " << order_changes << endl;
}
iter++;
}
// 最終統計
for (int i = 0; i < MAX_ROUTE_POINTS; i++) {
action_stats[best.actions[i].order]++;
}
cerr << "Phase 2 complete: " << iter << " iterations, " << improvements << " improvements, " << order_changes << " order changes" << endl;
cerr << "Best order-optimized score: " << best.score << endl;
cerr << "Action distribution: NONE=" << action_stats[0] << ", COPY=" << action_stats[1]
<< ", WRITE=" << action_stats[2] << ", C→W=" << action_stats[3] << ", W→C=" << action_stats[4] << endl;
// 最適解を適用して操作列を生成
vector<char> operations = phase1_result.operations;
// Phase2の順序最適化連続巡回操作を追加
A = phase1_result.grid_state;
int s = phase1_result.s_value;
int currentR = phase1_result.end_position.first;
int currentC = phase1_result.end_position.second;
// 連続巡回の操作生成（順序最適化）
for (int i = 0; i < route.size() && operations.size() < T; i++) {
int targetR = route[i].first;
int targetC = route[i].second;
// 効率的な移動
while ((currentR != targetR || currentC != targetC) && operations.size() < T) {
if (currentR < targetR) {
operations.push_back('D');
currentR++;
} else if (currentR > targetR) {
operations.push_back('U');
currentR--;
} else if (currentC < targetC) {
operations.push_back('R');
currentC++;
} else {
operations.push_back('L');
currentC--;
}
}
if (operations.size() >= T) break;
// 順序最適化アクション実行
ActionOrder order = best.actions[i].order;
if (order == COPY_ONLY && operations.size() < T) {
operations.push_back('C');
s ^= A[currentR][currentC];
}
else if (order == WRITE_ONLY && operations.size() < T) {
operations.push_back('W');
A[currentR][currentC] ^= s;
}
else if (order == COPY_THEN_WRITE && operations.size() + 1 < T) {
operations.push_back('C');
s ^= A[currentR][currentC];
operations.push_back('W');
A[currentR][currentC] ^= s;
}
else if (order == WRITE_THEN_COPY && operations.size() + 1 < T) {
operations.push_back('W');
A[currentR][currentC] ^= s;
operations.push_back('C');
s ^= A[currentR][currentC];
}
// NONE の場合は何もしない
}
cerr << "Generated " << operations.size() << " total operations (Phase1: " << phase1_result.operations.size() << ", Phase2: " << (operations.size() - phase1_result.operations.size()) << ")" << endl;
// 最終スコア確認
long long final_score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
final_score += A[i][j];
}
}
cerr << "Final grid score: " << final_score << endl;
// 順序最適化効果の分析
int total_double_actions = action_stats[3] + action_stats[4]; // C→W + W→C
int total_single_actions = action_stats[1] + action_stats[2]; // COPY + WRITE
cerr << "Order optimization: " << total_double_actions << " double actions, " << total_single_actions << " single actions" << endl;
return operations;
}
int main() {
cerr << "Order-Optimized Continuous Circuit Strategy - main10.cpp" << endl;
input();
cerr << "N=" << N << ", T=" << T << ", Grid size=" << N*N << endl;
cerr << "Time limit=" << TIME_LIMIT << "s" << endl;
if (N == 0 || T == 0) {
cerr << "Error: N or T is 0. Input reading failed." << endl;
return 1;
}
// Phase 1: main7.cppの手順で上2桁を1で揃える
Phase1Result phase1_result = phase1_bitWiseFill();
// Phase 2: 順序最適化連続巡回焼きなましを実行
vector<char> final_operations = phase2_orderOptimizedSimulatedAnnealing(phase1_result);
// 最終結果出力
cerr << "=== Final Result ===" << endl;
cerr << "Total operations: " << final_operations.size() << "/" << T << endl;
cerr << "Phase1 score: " << phase1_result.score << endl;
for (char op : final_operations) {
cout << op << endl;
}
return 0;
}