/***************************************************************************************** * XOR-Printer 10×10 ― “ランダム順+局所乱択” ベースライン * * ▼ アルゴリズム * 1. 100 マスの訪問順をシャッフル * 2. 各区間 (start → goal) で * - PATH_TRIALS 本の “ランダムな最短経路” を生成 * - 各経路について COPY_TRIALS 通りの Copy 位置を乱択 * - 目標マスで Write したときの増点が最大のものを採用 * - Write は **after > before の場合しか出さない**(減点禁止) * 3. 累計 1000 手、または 1.9 秒で打ち切り * 4. 余った手はランダムウォークしつつ Hill-Climb(増点なら必ず Write) * *****************************************************************************************/ #include using namespace std; /* ====== 型と定数 ====== */ using u32 = uint32_t; struct XY { int r, c; }; constexpr int N = 10; constexpr int MAX_OPS = 1000; constexpr long long TL_US = 1'900'000; // 1.9 秒で安全停止 constexpr int PATH_TRIALS = 20; // 各区間で試す経路本数 constexpr int COPY_TRIALS = 32; // 各経路で試す Copy 組み合わせ数 /* ====== 盤面・状態 ====== */ u32 A[N][N]; // 現在の値 u32 s = 0; // 手持ち値 XY pos{0,0}; // 現在位置 /* ====== 出力操作列 ====== */ vector OPS; inline bool ops_full() { return (int)OPS.size() >= MAX_OPS; } inline void emit(char op) { if (!ops_full()) OPS.push_back(op); } /* ====== 乱数ユーティリティ ====== */ mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template inline T rnd(T ub) { return uniform_int_distribution(0, ub - 1)(rng); } inline bool coin() { return uniform_int_distribution(0,1)(rng); } /* ====== タイムリミット ====== */ auto T0 = chrono::steady_clock::now(); inline bool time_over() { return chrono::duration_cast(chrono::steady_clock::now() - T0).count() > TL_US; } /* ====== 座標ヘルパ ====== */ inline int mdist(const XY& a, const XY& b) { return abs(a.r - b.r) + abs(a.c - b.c); } /* ------------------------------------------------------------ * ランダムな最短経路を 1 本生成 * – 戻り値: 移動後座標列 (goal を含む) * ----------------------------------------------------------*/ vector random_shortest_path(const XY& st, const XY& gl) { int dr = gl.r - st.r, dc = gl.c - st.c; vector moves; moves.insert(moves.end(), abs(dr), dr < 0 ? 'U' : 'D'); moves.insert(moves.end(), abs(dc), dc < 0 ? 'L' : 'R'); shuffle(moves.begin(), moves.end(), rng); vector path; path.reserve(moves.size()); XY cur = st; for (char mv : moves) { if (mv == 'U') --cur.r; else if (mv == 'D') ++cur.r; else if (mv == 'L') --cur.c; else ++cur.c; path.push_back(cur); } return path; // len == mdist } /* ------------------------------------------------------------ * 1 候補パスをシミュレーションして評価 * – Copy は copyMask の bit で指定 * – Write は「増点になる場合だけ」 ops の末尾に付ける * ----------------------------------------------------------*/ struct Cand { long long gain; // 得点増分 (>=0, 0 の場合は Write 無し) vector ops; // 操作列 u32 end_s; // 終点での手持ち s }; Cand simulate(const vector& path, uint32_t copyMask, u32 cur_s) { Cand res; res.gain = 0; vector& ops = res.ops; XY cur = pos; u32 tmp_s = cur_s; /* ---- 移動+Copy ---- */ for (size_t i = 0; i < path.size(); ++i) { const XY& nx = path[i]; // 移動 1 step if (nx.r < cur.r) ops.push_back('U'); else if (nx.r > cur.r) ops.push_back('D'); else if (nx.c < cur.c) ops.push_back('L'); else ops.push_back('R'); cur = nx; // Copy? if (copyMask & (1u << i)) { tmp_s ^= A[cur.r][cur.c]; ops.push_back('C'); } } /* ---- Write (必要なら) ---- */ u32 after = A[cur.r][cur.c] ^ tmp_s; if (after > A[cur.r][cur.c]) { res.gain = after - A[cur.r][cur.c]; ops.push_back('W'); } res.end_s = tmp_s; return res; } /* ------------------------------------------------------------ * 操作列を実際に適用(盤面・状態更新 & 出力) * – W は必ず再チェックして「増点時のみ」実行 * ----------------------------------------------------------*/ void apply_ops(const vector& ops) { for (char op : ops) { if (ops_full()) break; if (op == 'U' || op == 'D' || op == 'L' || op == 'R') { emit(op); if (op == 'U') --pos.r; else if (op == 'D') ++pos.r; else if (op == 'L') --pos.c; else ++pos.c; } else if (op == 'C') { emit('C'); s ^= A[pos.r][pos.c]; } else if (op == 'W') { u32 after = A[pos.r][pos.c] ^ s; if (after > A[pos.r][pos.c] && !ops_full()) { emit('W'); A[pos.r][pos.c] = after; // 書き込み確定 } } } } /* ============================== * main * ============================*/ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* --- 入力 --- */ int Nin, Tlim; // N=10, T=1000 固定 cin >> Nin >> Tlim; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> A[i][j]; /* --- 100 マスの訪問順をシャッフル --- */ vector order(100); iota(order.begin(), order.end(), 0); shuffle(order.begin(), order.end(), rng); /* --- 各区間で乱択探索 --- */ for (int k = 0; k < 100 && !ops_full() && !time_over(); ++k) { XY goal{ order[k] / 10, order[k] % 10 }; if (goal.r == pos.r && goal.c == pos.c) continue; long long bestGain = -1; Cand bestCand; for (int p = 0; p < PATH_TRIALS && !time_over(); ++p) { auto path = random_shortest_path(pos, goal); for (int t = 0; t < COPY_TRIALS; ++t) { uint32_t mask = rnd(1u << path.size()); Cand cand = simulate(path, mask, s); if ((int)OPS.size() + (int)cand.ops.size() > MAX_OPS) continue; if (cand.gain > bestGain) { bestGain = cand.gain; bestCand = std::move(cand); } } } /* bestGain < 0 なら Write 無しの短経路を使う */ if (bestGain < 0) { auto plain = random_shortest_path(pos, goal); bestCand = simulate(plain, 0u, s); // Write 無し (gain=0) } apply_ops(bestCand.ops); s = bestCand.end_s; // Copy 分だけ更新 } /* --- 余った手:ランダムウォーク Hill-Climb --- */ const int d4[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; while (!ops_full() && !time_over()) { int dir = rnd(4); XY nxt{ pos.r + d4[dir][0], pos.c + d4[dir][1] }; if (nxt.r < 0 || nxt.r >= N || nxt.c < 0 || nxt.c >= N) continue; /* 移動 */ emit(dir == 0 ? 'U' : dir == 1 ? 'D' : dir == 2 ? 'L' : 'R'); pos = nxt; /* Write が増点なら必ず実行 */ u32 after = A[pos.r][pos.c] ^ s; if (after > A[pos.r][pos.c] && !ops_full()) { emit('W'); A[pos.r][pos.c] = after; } else if (!ops_full() && coin()) { // 50 % で Copy 試行 emit('C'); s ^= A[pos.r][pos.c]; } } /* --- 出力(ヘッダ行なし) --- */ for (char c : OPS) cout << c << '\n'; return 0; }