백준2582 동전 뒤집기 2

작성일 | In

문제 링크

  • http://icpc.me/2582

문제 출처

  • 2006 KOI 지역본선 중등부 4번
  • 2006 KOI 지역본선 고등부 4번

사용 알고리즘

  • 시뮬레이티드 어닐링

풀이

구사과님 블로그를 참고하면서 풀면 됩니다.

온도 감률과 볼츠만 상수는… 손으로 파라메트릭 서치를 한다는 기분으로 열심히 조절하시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
ll arr[33];

int main(){
	mt19937 rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	uniform_int_distribution<int> ran(0, n-1);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			char c; cin >> c;
			arr[i] <<= 1;
			if(c == 'H') arr[i] |= 1;
		}
	}

	int ans = n*n;
	int a = 0, b = 0;
	int prv = n*n;
	double t = 1.0, k = 2.5;
	for(int i=0; i<10101; i++){
		b = a ^ (1 << ran(rd));
		int now = 0;
		for(int j=0; j<n; j++){
			int t = __builtin_popcount(arr[j] ^ b);
			now += min(t, n-t);
		}
		double nowP = exp((prv - now) / (k * t));
		if(nowP > (double)ran(rd) / (n-1)){
			a = b; prv = now;
		}
		ans = min(ans, prv);
		k *= 0.9999;
	}
	cout << ans;
}