ログイン
新規登録
AtsuoCoder Optimization Contest 001
読込中…
Home
Tasks
Clar
Submissions
Standings
提出 e3f5d075-c760-4860-a043-5432c9764562
コード
#ifndef MAIN #define MAIN #include __FILE__ struct XORShiftRandom { uint64_t x = 88172645463325252ULL; inline uint64_t next() { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } inline int nextInt(int mod) { return next() % mod; } inline double nextDouble() { return (double)next() / (double)((uint64_t)-1); } } rnd; struct Timer { chrono::high_resolution_clock::time_point start; Timer() { reset(); } void reset() { start = chrono::high_resolution_clock::now(); } double get() { auto now = chrono::high_resolution_clock::now(); return chrono::duration<double>(now - start).count(); } } timer; struct OpData { int id; int h, w, a, b; }; struct CmdData { int op_id; int x, y; }; int n, t; vector<vector<int>> a_init, b_target; vector<int> a_flat, b_flat; vector<OpData> ops; vector<vector<vector<int>>> ops_by_color(50, vector<vector<int>>(50)); namespace ThemeB { // AtsuoCoder だと 0.05s くらい誤差がある constexpr double TIME_LIMIT = 2.90; constexpr int MAX_OPS_USE = 3; constexpr double BEAM_TIME_RATIO = 0.2; constexpr double BEAM_TIME = TIME_LIMIT * BEAM_TIME_RATIO; struct State { vector<int> grid; vector<CmdData> history; vector<char> op_counts; int current_diff; State() { grid = a_flat; op_counts.resize(t, 0); current_diff = 0; rep(i, n * n) { int diff = grid[i] - b_flat[i]; current_diff += diff * diff; } } int eval_diff(int op_idx, int x, int y) { const OpData &op = ops[op_idx]; int diff = 0; if (x + op.h > n || y + op.w > n) return INT_MAX / 3; rep(i, op.h) { rep(j, op.w) { int val = grid[(x + i) * n + (y + j)]; if (val == op.a) { int old_err = val - b_flat[(x + i) * n + (y + j)]; int new_err = op.b - b_flat[(x + i) * n + (y + j)]; diff += (new_err * new_err) - (old_err * old_err); } } } return diff; } void apply(int op_idx, int x, int y, int diff) { const OpData &op = ops[op_idx]; rep(i, op.h) { rep(j, op.w) { if (grid[(x + i) * n + (y + j)] == op.a) { grid[(x + i) * n + (y + j)] = op.b; } } } current_diff += diff; op_counts[op_idx]++; history.push_back({op_idx, x, y}); } }; // もっと調節したい vector<int> get_worst_indices(const vector<int> &grid, int k) { vector<pair<long long, int>> diffs; diffs.reserve(n * n); rep(i, n * n) { long long d = grid[i] - b_flat[i]; if (d != 0) { diffs.push_back({d * d, i}); } } if ((int)diffs.size() > k) { partial_sort(diffs.begin(), diffs.begin() + k, diffs.end(), greater<pair<long long, int>>()); diffs.resize(k); } vector<int> res; for (auto &p : diffs) res.push_back(p.second); return res; } State beam_search() { constexpr int BEAM_WIDTH = 2000; constexpr int BEAM_DEPTH = inf; vector<State *> beam; beam.push_back(new State()); rep(i, BEAM_DEPTH) { if (timer.get() > BEAM_TIME) { cerr << "Beam search stopped at depth " << i << endl; break; } struct Candidate { int parent_idx; int op_idx; int x, y; int diff; int score; }; vector<Candidate> candidates; rep(j, beam.size()) { State *state = beam[j]; vector<int> targets = get_worst_indices(state->grid, 5); if (targets.empty()) continue; for (int idx : targets) { int ty = idx / n; int tx = idx % n; int current_val = state->grid[idx]; int target_val = b_flat[idx]; const vector<int> &c_ops = ops_by_color[current_val][target_val]; int trials = 0; for (int op_idx : c_ops) { if (state->op_counts[op_idx] >= MAX_OPS_USE) continue; const auto &op = ops[op_idx]; int r_min = max(0, ty - op.h + 1); int r_max = min(n - op.h, ty); int c_min = max(0, tx - op.w + 1); int c_max = min(n - op.w, tx); for (int r = r_min; r <= r_max; r++) { for (int c = c_min; c <= c_max; c++) { int diff = state->eval_diff(op_idx, r, c); if (diff < 0) { int penalty = 50.0; int new_score = state->current_diff - diff - penalty; candidates.push_back(Candidate{j, op_idx, r, c, diff, new_score}); } } } trials++; if (trials > 5) break; } } } if (candidates.empty()) break; sort(all(candidates), [](const Candidate &a, const Candidate &b) { return a.score > b.score; }); vector<State *> next_states; rep(k, min(candidates.size(), BEAM_WIDTH)) { State *parent = beam[candidates[k].parent_idx]; State *next_state = new State(*parent); next_state->apply(candidates[k].op_idx, candidates[k].x, candidates[k].y, candidates[k].diff); next_states.push_back(next_state); } for (State *s : beam) { delete s; } beam = next_states; } State best_state = *beam[0]; for (State *s : beam) { if (s->current_diff + s->history.size() < best_state.current_diff + best_state.history.size()) { best_state = *s; } delete s; } return best_state; } int calc_score_full(const vector<CmdData> &cmd) { vector<vector<int>> grid = a_init; rep(i, cmd.size()) { const OpData &op = ops[cmd[i].op_id]; rep(x, op.h) { rep(y, op.w) { if (grid[cmd[i].x + x][cmd[i].y + y] == op.a) { grid[cmd[i].x + x][cmd[i].y + y] = op.b; } } } } int diff = 0; rep(i, n) { rep(j, n) { int d = grid[i][j] - b_target[i][j]; diff += d * d; } } return diff; } int simulate(const vector<CmdData> &cmds, vector<int> &workspace) { copy(a_flat.begin(), a_flat.end(), workspace.begin()); for (const auto &cmd : cmds) { const auto &op = ops[cmd.op_id]; for (int i = 0; i < op.h; ++i) { int row_offset = (cmd.x + i) * n + cmd.y; for (int j = 0; j < op.w; ++j) { if (workspace[row_offset + j] == op.a) { workspace[row_offset + j] = op.b; } } } } int ssd = 0; for (int i = 0; i < n * n; ++i) { int d = workspace[i] - b_flat[i]; ssd += d * d; } return ssd + cmds.size(); } int erase_param, shift_param; void simulated_annealing(vector<CmdData> &best_cmds) { vector<int> workspace(n * n); int current_score = simulate(best_cmds, workspace); int best_score = current_score; vector<CmdData> saved_best_cmds = best_cmds; double start_temp = 200.0; double end_temp = 1.0; int iter = 0; vector<int> op_counts(t, 0); for (auto &c : best_cmds) op_counts[c.op_id]++; // 削除操作は N が大きければ大きいほど有効そう int w1 = n * 2.5; // シフト操作は N が小さければ小さいほど有効そう int w2 = 0; // 追加操作は中間くらい int w3 = (40) * 1.0; int split1 = w1 * 128 / (w1 + w2 + w3); int split2 = (w1 + w2) * 128 / (w1 + w2 + w3); cerr << "Trying on " << split1 << " / " << split2 << " splits." << endl; double now = timer.get(); while (true) { iter++; if ((iter & 127) == 0) { now = timer.get(); if (now > TIME_LIMIT) break; split1 = TIME_LIMIT * 128 / (now * 3.5) + 10; } double progress = (now - (TIME_LIMIT * 0.4)) / (TIME_LIMIT * 0.6); double temp = start_temp + (end_temp - start_temp) * progress; int type = rnd.next() & 127; vector<CmdData> next_cmds = best_cmds; vector<int> next_op_counts = op_counts; bool possible = true; // 後半に向かって削除を少なくしてもいい if (type < split1) { if (!next_cmds.empty()) { int idx = rnd.nextInt(next_cmds.size()); next_op_counts[next_cmds[idx].op_id]--; next_cmds.erase(next_cmds.begin() + idx); } else { possible = false; } } // else if (type < split2) // { // if (!next_cmds.empty()) // { // int idx = rnd.nextInt(next_cmds.size()); // CmdData &c = next_cmds[idx]; // const auto &op = ops[c.op_id]; // int dr = rnd.nextInt(3) - 1; // int dc = rnd.nextInt(3) - 1; // c.x += dr; // c.y += dc; // if (c.x < 0 || c.y < 0 || c.x + op.h > n || c.y + op.w > n) // possible = false; // } // else // { // possible = false; // } // } else { int op_idx = rnd.nextInt(t); if (next_op_counts[op_idx] < MAX_OPS_USE) { const auto &op = ops[op_idx]; int r = rnd.nextInt(n - op.h + 1); int c = rnd.nextInt(n - op.w + 1); next_cmds.push_back({op_idx, r, c}); next_op_counts[op_idx]++; } else { possible = false; } } if (possible) { int next_score_val = simulate(next_cmds, workspace); int delta = next_score_val - current_score; if (delta <= 0 || rnd.nextDouble() < exp(-delta / temp)) { best_cmds = next_cmds; op_counts = next_op_counts; current_score = next_score_val; if (current_score < best_score) { best_score = current_score; saved_best_cmds = best_cmds; } } } } cerr << "SA finished after " << iter << " iterations." << endl; best_cmds = saved_best_cmds; } void solve() { a_init.resize(n, vector<int>(n)); b_target.resize(n, vector<int>(n)); rep(i, n) rep(j, n) cin >> a_init[i][j]; rep(i, n) rep(j, n) cin >> b_target[i][j]; a_flat.reserve(n * n); b_flat.reserve(n * n); rep(i, n * n) { a_flat.push_back(a_init[i / n][i % n]); b_flat.push_back(b_target[i / n][i % n]); } ops.resize(t); rep(i, t) cin >> ops[i].h >> ops[i].w >> ops[i].a >> ops[i].b, ops[i].id = i; rep(i, t) { ops_by_color[ops[i].a][ops[i].b].push_back(i); } // デバッグ用 timer.reset(); // State init = beam_search(); // cerr << "Beam search: " << init.history.size() << " ops, diff = " << init.current_diff << ", time = " << fixed << setprecision(6) << timer.get() << "s" << endl; // vector<CmdData> cmd = init.history; vector<CmdData> cmd; simulated_annealing(cmd); cout << cmd.size() << '\n'; rep(i, cmd.size()) { cout << cmd[i].op_id << ' ' << cmd[i].x << ' ' << cmd[i].y << '\n'; } int ssd = calc_score_full(cmd); cerr << "Score: " << fixed << setprecision(9) << (1e9 * n * n / (n * n + cmd.size() + ssd)) << endl; } } void _main() { cin >> n >> t; ThemeB::solve(); } #else #ifdef DEBUG #pragma GCC optimize("O0") #else #ifdef ONLINE_JUDGE #pragma GCC target("avx2") #endif #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <atcoder/all> using namespace atcoder; using modint10 = modint1000000007; using modint9 = modint998244353; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector<string> strvec; constexpr ll mod10 = 1000000007; constexpr ll mod9 = 998244353; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repf(i, s, n) for (int i = s; i < (int)(n); i++) #define repr(i, n) for (int i = n - 1; i >= 0; i--) #define reprt(i, e, n) for (int i = n - 1; i >= e; i--) #define rep2(i, j, n, m) rep(i, n) rep(j, m) template <class... Args> void __y_input(Args &...arg) { (cin >> ... >> arg); } template <class... Args> void __y_input_vec_1(int p, Args &...args) { (cin >> ... >> args[p]); } template <class... Args> void __y_input_vec_2(int p, int q, Args &...args) { (cin >> ... >> args[p][q]); } template <class Arg> void __y_input_vec_resize(int size, Arg &arg) { arg.resize(size); } template <class Arg_t> void __y_input_vec_resize_2(int n, int m, vector<Arg_t> &arg) { arg.assign(n, Arg_t(m)); } template <class... Args> void __y_input_vec(int n, Args &...args) { (__y_input_vec_resize(n, args), ...); rep(i, n) { (__y_input_vec_1(i, args), ...); } } template <class... Args> void __y_input_vec2(int n, int m, Args &...args) { (__y_input_vec_resize_2(n, m, args), ...); rep2(i, j, n, m) { (__y_input_vec_2(i, j, args), ...); } } template <class T, class... Args> void SyncSort(vector<T> &vec, vector<Args> &...args) { vector<pair<T, tuple<Args...>>> z; rep(i, vec.size()) { z.push_back({vec[i], make_tuple(args.at(i)...)}); } sort(z.begin(), z.end()); rep(i, vec.size()) { vec[i] = z[i].first; tie(args[i]...) = z[i].second; } } #define cint(...) \ int __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cdbl(...) \ double __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cstr(...) \ string __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cit(t, ...) \ t __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cvec(n, ...) \ vector<int> __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvect(t, n, ...) \ vector<t> __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvec2(n, m, ...) \ vector<vector<int>> __VA_ARGS__; \ __y_input_vec2(n, m, __VA_ARGS__) #define cvec2t(t, n, m, ...) \ vector<vector<t>> __VA_ARGS__; \ __y_input_vec2(n, m, __VA_ARGS__) #define cvecs(n, ...) cvect(string, n, __VA_ARGS__) #define yn(bl) (bl ? "Yes" : "No") #define all(v) v.begin(), v.end() template <typename T> using vec2 = vector<vector<T>>; template <typename T> using vec3 = vector<vector<vector<T>>>; template <typename T> constexpr T limit() { return numeric_limits<long long>::max(); } constexpr ll inf = limit<ll>() / 100; template <typename T> constexpr T limit(T _) { return numeric_limits<long long>::max(); } typedef array<int, 2> xy; typedef array<int, 3> xyz; template <typename T> inline void sort(T &vec) { return sort(vec.begin(), vec.end()); } template <typename T> inline void rsort(T &vec) { return sort(vec.rbegin(), vec.rend()); } template <typename T> inline vector<vector<T>> rotate90(const vector<vector<T>> &vec) { vector<vector<T>> res(vec[0].size(), vector<T>(vec.size())); rep(i, vec.size()) { rep(j, vec[0].size()) { res[j][vec.size() - i - 1] = vec[i][j]; } } return res; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (T val : vec) { os << val << ' '; } return os; } template <typename T> vector<T> &operator+=(vector<T> &vec, const T &val) { vec.push_back(val); return vec; } template <typename T> vector<T> &operator+=(vector<T> &vec, const vector<T> &val) { vec.insert(vec.end(), val.begin(), val.end()); return vec; } template <typename T> vector<T> &operator+=(vector<T> &vec, const initializer_list<T> &val) { vec.insert(vec.end(), val.begin(), val.end()); return vec; } template <typename T> vector<vector<T>> operator*(vector<T> &vec, int val) { return vector<vector<T>>(val, vec); } // Libraries Begin map<int, int> prime_factorize(int n) { map<int, int> res; for (int i = 2; i * i <= n; i += 1 + i > 2) { while (n % i == 0) { res[i]++; n /= i; } } if (n != 1) { res[n]++; } return res; } // Libraries End // Defines template <typename... T> common_type_t<T...> __yc_max(T... args) { return max(initializer_list<common_type_t<T...>>{args...}); } template <typename... T> common_type_t<T...> __yc_min(T... args) { return min(initializer_list<common_type_t<T...>>{args...}); } template <typename T> vector<T> iota(size_t n, T start = 0) { vector<T> res(n); iota(all(res), start); return res; } #define max(...) __yc_max(__VA_ARGS__) #define min(...) __yc_min(__VA_ARGS__) // Defines End int isqrt(int x) { int ok = 0, ng = 3037000500; while (ng - ok > 1) { int mid = (ok + ng) / 2; if (mid * mid <= x) { ok = mid; } else { ng = mid; } } return ok; } void _main(); signed main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); _main(); return 0; } #endif // 自分ここまでよくこのコード書いた！ // __ ====^^==== //===\\ ======= ||=====\\ ||====== ||=====\| + // //\\ || // \\ // \\ || \| || || || + // // \\ || || || || || || ||====== ||=====// + // //====\\ || \\ // \\ // || /| || || \\\ + // // \\ || \===// \=====// ||=====// ||====== || \\\ +
結果
問題
点数
言語
結果
実行時間
メモリ
A - Replace() は Replace() されました
10281744
C++
AC
2941 ms
4932 KiB
コンパイルエラー
Main.cpp: In function 'ThemeB::State ThemeB::beam_search()': Main.cpp:151:44: warning: overflow in conversion from 'long long int' to 'int' changes value from '92233720368547758' to '2061584302' [-Woverflow] 151 | constexpr int BEAM_DEPTH = inf; | ^~~ In file included from Main.cpp:3: Main.cpp: In instantiation of 'std::common_type_t<T ...> __yc_min(T ...) [with T = {long unsigned int, int}; std::common_type_t<T ...> = long unsigned int]': Main.cpp:223:4: required from here Main.cpp:733:58: warning: narrowing conversion of 'args#1' from 'int' to 'long unsigned int' [-Wnarrowing] 733 | return min(initializer_list<common_type_t<T...>>{args...}); | ^~~~ Main.cpp:733:58: warning: narrowing conversion of 'args#1' from 'int' to 'long unsigned int' [-Wnarrowing]