#include // clang-format off #ifdef ONLINE_JUDGE const int LOCAL = 0; #else const int LOCAL = 0; #endif using namespace std; #define debug1(a) {if(LOCAL){cerr<<#a<<":"<; namespace marathon { std::mt19937 engine(0); clock_t start_time; double now() { return CLOCK_RATIO * (clock() - start_time) / CLOCKS_PER_SEC; } void marathon_init() { start_time = clock(); std::random_device seed_gen; engine.seed(seed_gen()); } template void vecremove_first(std::vector &vec, T elem) { // elemに一致する最初の要素を削除 vec.erase(std::find(vec.begin(), vec.end(), elem)); } }; // namespace marathon const int inf = 1e9; const int N = 10; const int T = 1000; const int N2 = 100; int INIT_TBL[N2]; int distance_table[N2][N2]; const int8_t COPY = -1; const int8_t WRITE = -2; string int_to_bits(int x) { string res; for (int b = 19; b >= 0; b--) { if ((x >> b) & 1) { res.push_back('1'); } else { res.push_back('0'); } } return res; } void output(vector ops) { int player = 0; for (auto op : ops) { if (op == COPY) { cout << "C" << endl; } else if (op == WRITE) { cout << "W" << endl; } else { pii p = {player / N, player % N}; pii g = {op / N, op % N}; while (p != g) { if (p.first < g.first) { cout << "D" << endl; p.first++; } else if (p.first > g.first) { cout << "U" << endl; p.first--; } else if (p.second < g.second) { cout << "R" << endl; p.second++; } else if (p.second > g.second) { cout << "L" << endl; p.second--; } else { assert(0); } } player = op; } } } struct board_t { int total_cost; int tbl[N2]; int x; int player; }; pair> greedy(board_t init_bd, vector init_ops) { vector ops = init_ops; auto bd = init_bd; while (true) { pair bestop = {-1, {-1, -1}}; for (int s = 0; s < N2; s++) { for (int t = 0; t < N2; t++) { int cost = distance_table[bd.player][s] + distance_table[s][t] + 2; // if (cost > 15) continue; if (cost > T - bd.total_cost) continue; int y = bd.x ^ bd.tbl[s]; int oldval = bd.tbl[t]; int newval = bd.tbl[t] ^ y; if (newval <= oldval) continue; bestop = max(bestop, {newval - oldval, {s, t}}); } } if (bestop.first < 0) break; { int8_t s = bestop.second.first; int8_t t = bestop.second.second; ops.push_back(s); ops.push_back(COPY); ops.push_back(t); ops.push_back(WRITE); bd.x = bd.x ^ bd.tbl[s]; bd.tbl[t] = bd.x ^ bd.tbl[t]; bd.total_cost += distance_table[bd.player][s] + distance_table[s][t] + 2; bd.player = t; } } return {bd, ops}; } pair> rulebased(board_t init_bd, vector init_ops) { int TS = T - marathon::engine() % 100; // XORの性質を考えると「上の桁から順に 0→1 にする」のがよい auto bd = init_bd; auto ops = init_ops; auto op_move = [&](int u) { bd.total_cost += distance_table[bd.player][u]; bd.player = u; ops.push_back(u); assert(bd.total_cost <= T); }; auto op_write = [&]() { bd.total_cost += 1; bd.tbl[bd.player] = bd.x ^ bd.tbl[bd.player]; ops.push_back(WRITE); assert(bd.total_cost <= T); }; auto op_copy = [&]() { bd.total_cost += 1; bd.x = bd.x ^ bd.tbl[bd.player]; ops.push_back(COPY); assert(bd.total_cost <= T); }; bitset ignored = 0; for (int bit = 19; bit >= 0; bit--) { bool must_change = false; { if (((bd.x >> bit) & 1) == 0) must_change = true; for (int b = bit + 1; b <= 19; b++) { if (((bd.x >> b) & 1) > 0) must_change = true; } } if (must_change) { pii bestmv = {inf, -1}; for (int u = 0; u < N2; u++) { if (ignored[u]) continue; int y = bd.x ^ bd.tbl[u]; if (((y >> bit) & 1) == 0) continue; bool ok = true; for (int b = bit + 1; b <= 19; b++) { if ((y >> b) & 1) ok = false; } if (ok) { bestmv = min(pii{(distance_table[bd.player][u] + 1) * 100 + marathon::engine() % 100, u}, bestmv); } } if (bestmv.first > TS - bd.total_cost) break; { int u = bestmv.second; op_move(u); op_copy(); } } // debug3(bit, bd.x, bd.player); vector goals; vector nongoals; for (int u = 0; u < N2; u++) { if (ignored[u]) continue; if ((bd.x ^ bd.tbl[u]) > bd.tbl[u]) { goals.push_back(u); } else { nongoals.push_back(u); } } { { bitset isgoal = 0; for (auto g : goals) { isgoal[g] = 1; } pair> min_g = {1e9, vector()}; for (int parity = 0; parity <= 1; parity++) { { vector gorder; for (int r = 0; r < N; r++) { if (r % 2 == parity) { for (int c = 0; c < N; c++) { if (isgoal[r * N + c]) gorder.push_back(r * N + c); } } else { for (int c = N - 1; c >= 0; c--) { if (isgoal[r * N + c]) gorder.push_back(r * N + c); } } } int d = distance_table[bd.player][gorder[0]]; for (int i = 1; i < gorder.size(); i++) { d += distance_table[gorder[i - 1]][gorder[i]]; } d += marathon::engine() % 5; min_g = min(min_g, {d, gorder}); } { vector gorder; for (int r = 0; r < N; r++) { // 転置 if (r % 2 == parity) { for (int c = 0; c < N; c++) { if (isgoal[c * N + r]) gorder.push_back(c * N + r); } } else { for (int c = N - 1; c >= 0; c--) { if (isgoal[c * N + r]) gorder.push_back(c * N + r); } } } int d = distance_table[bd.player][gorder[0]]; for (int i = 1; i < gorder.size(); i++) { d += distance_table[gorder[i - 1]][gorder[i]]; } d += marathon::engine() % 5; min_g = min(min_g, {d, gorder}); } { vector gorder; for (int r = N - 1; r >= 0; r--) { if (r % 2 == parity) { for (int c = 0; c < N; c++) { if (isgoal[r * N + c]) gorder.push_back(r * N + c); } } else { for (int c = N - 1; c >= 0; c--) { if (isgoal[r * N + c]) gorder.push_back(r * N + c); } } } int d = distance_table[bd.player][gorder[0]]; for (int i = 1; i < gorder.size(); i++) { d += distance_table[gorder[i - 1]][gorder[i]]; } d += marathon::engine() % 5; min_g = min(min_g, {d, gorder}); } { vector gorder; for (int r = N - 1; r >= 0; r--) { if (r % 2 == parity) { for (int c = 0; c < N; c++) { if (isgoal[c * N + r]) gorder.push_back(c * N + r); } } else { for (int c = N - 1; c >= 0; c--) { if (isgoal[c * N + r]) gorder.push_back(c * N + r); } } } int d = distance_table[bd.player][gorder[0]]; for (int i = 1; i < gorder.size(); i++) { d += distance_table[gorder[i - 1]][gorder[i]]; } d += marathon::engine() % 5; min_g = min(min_g, {d, gorder}); } } goals = min_g.second; } while (goals.size()) { pii min_g = {inf, inf}; for (auto g : goals) { min_g = min(min_g, {(distance_table[bd.player][g] + 1) * 100 + marathon::engine() % 100, g}); break; } if (min_g.first / 100 > TS - bd.total_cost) break; { int g = min_g.second; op_move(g); op_write(); marathon::vecremove_first(goals, g); } } if (goals.size() >= 1) break; if (bit > 0 && bit < 19) { pair bestpair = {inf, {inf, inf}}; // 1110と、1111を1個ずつ確保 int nbit = bit - 1; vector zero; vector one; for (auto g : nongoals) { if ((bd.tbl[g] >> nbit) & 1) { one.push_back(g); } else { zero.push_back(g); } } // debug2(one.size(), zero.size()); for (auto z : zero) { for (auto o : one) { bestpair = min(bestpair, {(distance_table[bd.player][z] + distance_table[z][o]) * 100 + marathon::engine() % 100, {z, o}}); } } if (bestpair.first >= inf) break; int s = bestpair.second.first; int t = bestpair.second.second; // debug2(bit, int_to_bits(bd.x)); if (distance_table[bd.player][s] + distance_table[s][t] + 4 > TS - bd.total_cost) break; op_move(s); op_write(); op_copy(); op_write(); op_move(t); op_copy(); // debug3(bit, int_to_bits(bd.x), bd.total_cost); ignored[s] = 1; } } } // debug2("rulebased end", bd.total_cost); return {bd, ops}; } pair> solve() { vector ops; board_t bd; bd.player = 0; bd.x = 0; bd.total_cost = 0; for (int u = 0; u < N2; u++) { bd.tbl[u] = INIT_TBL[u]; } tie(bd, ops) = rulebased(bd, ops); tie(bd, ops) = greedy(bd, ops); int score = 0; for (int u = 0; u < N2; u++) { score += bd.tbl[u]; } return {score, ops}; } int main() { marathon::marathon_init(); int n, t; cin >> n >> t; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { cin >> INIT_TBL[r * N + c]; } } for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { distance_table[r * N + c][i * N + j] = abs(r - i) + abs(c - j); } } } } pair> best; best.first = -1; for (int loop = 0; marathon::now() < 1800; loop++) { int s; vector ops; tie(s, ops) = solve(); best = max(best, {s, ops}); if (loop % 100 == 0) debug3(loop, s, best.first); } cerr << "score==" << best.first << endl; output(best.second); return 0; }