APIO 2013 interference

문제 링크:https://oj.uz/problem/view/APIO13_interference

문제 보기 - Interference (APIO13_interference) :: oj.uz

답을 최소화하기 위하서 나는 hill climbing 기법을 사용했다. 이 기법은 현재 상태에서 인접한(원소 차이가 하나인) 해 중 가장 좋은 해를 찾고, 그 해로 이동하는 것을 반복하는 기법이다. 이 기법을 사용해서 변화가 없을 때까지 탐색하고, 랜덤한 해로 이동하는 것을 반복해서 답을 구했다.

코드:

#include <iostream>
#include <algorithm>
#include <random>
#include <vector>
using namespace std;
int N;
random_device rd;
mt19937 gen(rd());
struct x
{
	int arr[101];
	int c[101];
	int r;
	x()
	{
		memset(arr, 0, sizeof(arr));
		memset(c, 0, sizeof(c));
		r = 0;
	}
	void ch(int n, int k)
	{
		int i;
		for (i = 1; i < N; i++)
		{
			if (n - i > 0)
			{
				c[i] -= arr[n - i] * (arr[n]-k);
			}
			if (n + i <= N)
			{
				c[i] -= arr[n + i] * (arr[n]-k);
			}
		}
		arr[n] = k;
		r = 0;
		for (i = 1; i < N; i++)
		{
			r += c[i] * c[i];
		}
	}
	void s()
	{
		int i;
		int c = arr[1];
		int bef = 1;
		for (i = 2; i <= N; i++)
		{
			if (c != arr[i])
			{
				arr[i] = c;
				if (bef < 10)
					cout << bef;
				else
					cout << (char)(bef - 10 + 'A');
				bef = 1;
			}
			else
			{
				bef++;
			}
		}
		if (bef < 10)
			cout << bef;
		else
			cout << (char)(bef - 10 + 'A');
	}
};
int main()
{
	cin >> N;
	int ans = 1 << 30;
	while (1)
	{
		int curans = 1 << 30;
		x r;
		int i;
		uniform_int_distribution<int>d1(0, 1);
		for (i = 0; i < N; i++)
		{
			r.ch(i + 1, 2 * d1(gen) - 1);
		}
		curans = r.r;
		uniform_int_distribution<int>d2(0, 3);
		while (1)
		{
			vector <pair<int, int>>xe;
			
			for (i = 0; i < N; i++)
			{
				x nr=r;
				nr.ch(i + 1, -r.arr[i + 1]);
				xe.push_back({ nr.r,i + 1 });
			}
			sort(xe.begin(), xe.end());
			int po = 0;
			while (1)
			{
				if (po == xe.size() || xe[po].first >= curans)
				{
					if (po == 0)
						goto T;
					po = 0;
				}
				if (d2(gen) == 0)
				{
					curans = xe[po].first;
					r.ch(xe[po].second, -r.arr[xe[po].second]);
					break;
				}
				po++;
			}
		}
		T:
		if (ans > curans)
		{
			ans = curans;
			cout<<'\n' << curans << '\n';
			r.s();
		}
		
	}
}

점수:

서브태스크 1~7:각 10점

서브태스크 8:7.37점

서브태스크 9:6.6점

서브태스크 10:6.7점