Codeforces Round #485 (Div. 2) 풀이

문제

코드

* div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다

A. Infinity Gauntlet

생략. 저는 map <string, string> 만들어놓고 하나씩 지웠습니다.

B. High School: Become Human

예상 외의 킬러 문제였습니다. 저를 포함한 많은 분들이 실수 다루는 데에 익숙하지 않다는 것을 잘 알 수 있었습니다.

$x^y$와 $y^x$을 직접 계산하려는 분들은 없을것이고, 보통 생각하는게 "양변에 로그를 씌우자!" 일 것입니다.

double x, y;
cin >> x >> y;

double t1 = y * log(x);
double t2 = x * log(y);

if (t1 > t2) cout << '>';
else if  (t1 < t2) cout << '<';
else cout << '=';

WA를 띄웁니다. 약간 이해가 안되긴 합니다. 제 컴퓨터에서는 잘 되는데 말입니다 ㅎㅎ...

실수는 거의 항상 오류를 포함하므로, 이렇게 써야 정석입니다.

#define EPS 1e-6

double x, y;
cin >> x >> y;

double t1 = y * log(x);
double t2 = x * log(y);

if (abs(t1 - t2) < EPS) cout << '=';
else {
	if (t1 > t2) cout << '>';
	else cout << '<';
}

1e-6이라는 값은 막 쓴건 아니고, 보통 입력 범위에 적당히 맞추어 쓰면 됩니다. double의 정확도는 10^-15정도이고 입력 숫자는 10^9까지라고 하였으므로 이 문제에서는 10^-6이 되겠네요.

조금 더 흥미로운 풀이법이 있습니다. 약간의 변형을 해봅시다.

$$x^y < y^x \Leftrightarrow y\log{x} < x\log{y} \Leftrightarrow \frac{y}{\log{y}} < \frac{x}{\log{x}}$$

여기서 마지막 함수를 주목할까요? $f(x) = \frac{x}{\log{x}}$라 하면, x, y에 대해 f(x)와 f(y)값을 비교하는 문제가 되었습니다.

f(x)는 x > e에서 증가함수입니다. e=2.718...이므로, x, y가 모두 3 이상이면 $f(y) < f(x) \Leftrightarrow y < x$입니다.

처음부터 다시 가보면 $x^y < y^x \Leftrightarrow y < x$이 되겠군요.

x나 y가 1 혹은 2일 경우만 잘 예외처리 해주면 훨씬 더 간단하게 비교할 수 있습니다.

C. Three displays

평범한 DP 문제입니다. y의 위치가 정해지면 렌트비용을 최소화하는 z를 뒤를 쭉 훑으며 찾을 수 있고, 이를 잘 저장해놓습니다.

y가 정해졌을 때 최소인 z는 O(1)에 구할 수 있으므로 x < y를 만족하는 쌍들을 모두 확인해보면 됩니다. 시간 복잡도는 $O(n^2)$.

D - Fair

여기서부턴 상당히 어렵습니다. 참고로 Div1의 A번 문제입니다.

도시의 수 n이 10만 정도, 물건의 수 k는 100입니다.

도시가 너무 많으므로 플로이드-워셜 알고리즘을 쓸 수는 없습니다. 우리가 궁금한 거는 "도시별로, 각 물건과의 거리"이므로 도시와 도시 사이의 최단 거리를 항상 알 필요는 없습니다.

한 가지 해법은, 각 물건별로, 물건을 가지고 있는 도시들을 모두 시작점으로 해서 BFS를 해주면 됩니다. 1번 물건을 가지고 있는 도시에서 탐색해서 n번 도시까지 거리가 d였다면, n번 도시에서 1번 물건을 가지고 있는 가장 가까운 도시와의 거리도 마찬가지로 d가 됩니다.

이러면 BFS를 최대 100번 수행하면 각 도시와의 물건사이의 거리를 모두 알 수 있습니다. 거리가 다 구해졌으니 이제 각 도시별로 가장 가까운 s개의 물품만 고르면 끝입니다.

E. Petr and Permutations

처음에는 딱 보고 뭔소린가 했습니다.

간단히 말하면, 랜덤 순열을 만드려고 하는데, 1,2,3, ..., n에서 시작하여 Petr는 3n번 숫자를 swap하고, Alex는 7n + 1번 swap해서 랜덤 순열을 만듭니다. 최종 만들어진 순열이 주어졌을 때 누가 만든 순열인지를 구하는 문제입니다.

풀기에 앞서 몇 가지 특징을 알아야 합니다. 순열을 swap해서 다른 순열을 만들 때, 정확히 두 그룹으로 나눌 수 있습니다. A그룹에서 swap을 하면 B그룹이 되고, B그룹에서 swap을 하면 A그룹이 되는 관계를 가지고 있습니다.

n = 3일 때의 예시는 다음과 같습니다.

A: 1 2 3 / 2 3 1 / 3 1 2   //   B: 1 3 2 / 2 1 3 / 3 2 1

처음 순열이 포함된 그룹을 A그룹이라고 하면, A그룹 원소는 n이 짝수일 때는 Petr가 만든 것이고, n이 홀수일 때는 Alex가 만들게 됩니다.

그러면 순열이 주어질 때 A그룹에 속해있는지, B그룹에 속해있는지를 어떻게 알 수 있을까요? 머리를 열심히 굴려본 결과 두 가지 특징을 찾았습니다.

1) 역순으로 된 쌍 갯수 세기

자기 뒤에 자기보다 작은 원소가 올 때, 역순으로 되어있다고 합니다.

예를 들어서 순열이 1, 4, 3, 2면 역순으로 된 쌍은 (4, 3), (4, 2), (3, 2) 3개네요.

역순으로 된 쌍의 수가 짝수개면 초기 순열과 같은 그룹입니다.

쌍의 수를 셀 때 $O(n^2)$으로 세면 당연히 시간초과고, 펜윅 트리를 사용하면 $O(n\log{n})$에 가능합니다.

2) union 갯수 세기

추상대수학 때 얼핏 들은 것을 곰곰히 생각하다 기억해냈습니다.

순열은 결국 loop로 나타낼 수 있는데, 이 loop의 수가 swap할 때마다 홀/짝이 바뀝니다.

예를 들어서 1, 4, 3, 2의 순열이면 다음과 같은 loop 3개가 있지요.

(1번) 1 -> 1

(2번) 2 -> 4 -> 2

(3번) 3 -> 3

이 방법을 사용하면 O(n)에 loop의 갯수를 셀 수 있습니다.

F. AND Graph

 아직 이 문제는 나에겐 이르ㄷ... 실력이 좀 늘면 다시 찾아오는걸로