提出 82fde745-a6cc-4309-9651-20fc1b5e75b3

コード

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;

struct Op
{
	int id, H, W, a, b;
};

struct ApplyOp
{
	int op_idx, x, y;
};

struct State
{
	vector<vector<int>> A;
	vector<ApplyOp> applied_ops;
	int score;
	array<char, 3000> used;
};

int calc_score(const vector<vector<int>> &A, const vector<vector<int>> &B)
{
	int score = 0;
	int N = A.size();
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			int diff = (int)A[i][j] - (int)B[i][j];
			score += diff * diff;
		}
	}
	return score;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, T;
	if (!(cin >> N >> T))
		return 0;
	vector<vector<int>> init_A(N, vector<int>(N)), B(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> init_A[i][j];
	auto atmp = init_A;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> B[i][j];
	vector<Op> ops(T);
	for (int t = 0; t < T; ++t)
	{
		ops[t].id = t;
		cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
	}
	const int LIMIT = 100000;

	clock_t clk = clock();
	struct XORShiftRandom
	{
		uint64_t x = 88172645463325252ULL;
		inline uint64_t operator()()
		{
			x ^= x << 13;
			x ^= x >> 7;
			x ^= x << 17;
			return x;
		}
		using result_type = uint64_t;
		constexpr static result_type min() { return 0; }
		constexpr static result_type max() { return UINT64_MAX; }
	} rng;

	constexpr int BEAM_WIDTH = 15;

	vector<State> states(1);
	states[0].A = init_A;
	states[0].score = calc_score(init_A, B);
	states[0].used.fill(0);

	while ((double)(clock() - clk) / CLOCKS_PER_SEC < 2.8)
	{
		vector<State> tmp_states = states;
		for (auto &[A, applied_ops, score, used] : states)
		{
			for (int _ = 0; _ < 3000; ++_)
			{
				int id = rng() % T, H = ops[id].H, W = ops[id].W, a = ops[id].a, b = ops[id].b;
				int uses = 0;
				if (used[id] < 3)
				{
					vector<vector<int>> pref(N + 1, vector<int>(N + 1, 0));
					bool anyPossible = false;
					for (int i = 0; i < N; ++i)
					{
						int rowSum = 0;
						for (int j = 0; j < N; ++j)
						{
							int w = 0;
							if (A[i][j] == a)
							{
								int before = (int)A[i][j] - (int)B[i][j];
								int after = (int)b - (int)B[i][j];
								w = after * after - before * before;
								anyPossible = true;
							}
							rowSum += w;
							pref[i + 1][j + 1] = pref[i][j + 1] + rowSum;
						}
					}
					if (!anyPossible)
						continue;
					int bestDelta = 0;
					int bestX = -1, bestY = -1;
					for (int x = 0; x + H <= N; ++x)
					{
						for (int y = 0; y + W <= N; ++y)
						{
							int x2 = x + H, y2 = y + W;
							int s = pref[x2][y2] - pref[x][y2] - pref[x2][y] + pref[x][y];
							if (s < bestDelta)
							{
								bestDelta = s;
								bestX = x;
								bestY = y;
							}
						}
					}
					if (bestX == -1)
						continue;
					for (int i = bestX; i < bestX + H; ++i)
					{
						for (int j = bestY; j < bestY + W; ++j)
						{
							if (A[i][j] == a)
								A[i][j] = b;
						}
					}
					applied_ops.push_back(ApplyOp{id, bestX, bestY});
					++used[id];
					score += bestDelta;
				}
			}
		}
		states.insert(states.end(), tmp_states.begin(), tmp_states.end());
		sort(states.begin(), states.end(), [](const State &s1, const State &s2)
			 { return s1.score < s2.score; });
		if (states.size() > BEAM_WIDTH)
			states.resize(BEAM_WIDTH);
	}

	auto &best_state = states[0];

	cout << best_state.applied_ops.size() << "\n";

	for (auto &[op_idx, x, y] : best_state.applied_ops)
	{
		cout << op_idx << " " << x << " " << y << "\n";
	}

	return 0;
}
結果

問題	点数	言語	結果	実行時間	メモリ
A - Replace() は Replace() されました	158622956	C++	AC	2945 ms	6720 KiB