提出 f2f7db5e-4801-4ddc-8eec-cb5bf0182d19

コード

#ifndef MAIN
#define MAIN
#include __FILE__

// AtsuoCoder だと 0.05s くらい誤差がある
constexpr double TIME_LIMIT = 2.80;
constexpr int MAX_OPS_USE = 3;
constexpr double BEAM_TIME_RATIO = 0.6;
constexpr double BEAM_TIME = TIME_LIMIT * BEAM_TIME_RATIO;

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));

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 = 50;
	constexpr int BEAM_DEPTH = 500;
	constexpr int BEAM_OPS_TRY = 50;

	vector<State *> beam;
	beam.push_back(new State());
	rep(i, BEAM_DEPTH)
	{
		if (timer.get() > BEAM_TIME)
			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, 10);
			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]++;

	while (true)
	{
		iter++;
		if ((iter & 127) == 0)
		{
			double now = timer.get();
			if (now > TIME_LIMIT)
				break;

			double progress = (now - (TIME_LIMIT * 0.4)) / (TIME_LIMIT * 0.6);
			double temp = start_temp + (end_temp - start_temp) * progress;

			int type = rnd.nextInt(100);

			vector<CmdData> next_cmds = best_cmds;
			vector<int> next_op_counts = op_counts;
			bool possible = true;

			if (type < 40)
			{
				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 < 70)
			{
				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;
					}
				}
			}
		}
		else
		{
			continue;
		}
	}
	best_cmds = saved_best_cmds;
}

void _main()
{
	cin >> n >> t;
	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 << init.history.size() << endl;
	cerr << init.current_diff << endl;
	vector<CmdData> cmd = init.history;
	if (!cmd.empty())
	{
		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;
}

#else

#ifdef DEBUG

#pragma GCC optimize("O0")

#else

#ifdef ONLINE_JUDGE

#pragma GCC target("avx2")

#endif

#pragma GCC optimize("O3")
#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() されました	11919619	C++ (gcc)	TLE	3015 ms	8432 KiB