[코포 라운드 글 #4] Codeforces Round #730 (Div. 2)

Codeforces Round #730 (Div. 2)

Dashboard - Codeforces Round #730 (Div. 2) - Codeforces

퍼포 : 1792

등수 : 1139

레이팅 변화 : 1633 -> 1675 (+42)

솔브 수 : 3

 

이번에 퍼플퍼포를 띄울수 있었는데 D1의 뇌절, C 맞왜틀 때문에 이루지 못하였다.

아쉬운 라운드였지만, 이젠 블루퍼포가 계속 나온다는 게 좀 기뻤다.

이제 더 노력해서 퍼플을 노려보자.

 

A. Exciting Bets

Problem - A - Codeforces

첫번째 출력 : |n-m|이다.

두번째 출력 : 두수를 |n-m|의 배수로 만드는 경우 중 최소 또는 0으로 만드는 경우 중에서 최소인 것을 찾으면 된다.

4분 AC.

코드

 

B. Customizing the Track 

Problem - B - Codeforces

어떤 배열의 두 수 절댓값 차의 총합을 최소화하는 문제이다.

절댓값 합이 최소가 되려면 같거나 차이가 거의 안나는 숫자들로 바꿔야 한다.

이때 우리는 이 원소들을 잘 조정해서 거의 다 비슷한 수들로 만든다고 했을때 

서로 같은 수거나 절댓값 차가 1인 수들로 만들수 있다는 거다.

예를 들어 8 3 6 11 5 2 1 7 10 4 같은 경우 이를 5 5 5 6 6 6 6 6 6 6 이런식으로 바꿀 수 있고 이것이 최소가 될 수 있다는 것이다.

절댓값의 차의 총합은 간단하게 구할 수 있다. 그냥 (n인 윈소들의 갯수)*(n+1인 윈소들의 갯수)이다.

8분 AC. (신기록 :yum:)

막상 설명하려고 하니 너무 힘드네

코드

 

D1. RPD and Rap Sheet (Easy Version)

Problem - D1 - Codeforces

n번만에 0~n-1까지의 값 중 하나를 찾으라는 건데 항상 가지고 있는 숫자가 문제에 나온 것처럼 바뀌어 나타난다.

그러므로 우리는 0~n-1까지의 값을 다 나타내기 위해 n-1부터 시작해서 (n-1)^x=n-2인 x의 값을 출력하면 된다는 거다.

x의 값은 쉽게 구할 수 있다. 우리는 임의의 자연수 t가 t^t=1이 성립된다는 것을 아니 이를 응용해보자.

양변에 ^(n-1)을 해주면

(n-1)^x^(n-1)=(n-2)^(n-1)

(n-1)^(n-1)^x=(n-2)^(n-1)

x=(n-2)^(n-1) 이 된다.

그러므로 i=n-1부터 시작해서 (i-1)^i의 값을 출력하면 된다.

43분 AC.

이걸 왜 뇌절했는지 아직도 이해가 안간다.

코드

 

C는 풀이는 맞았지만, 실수오차 때문에 뇌절하다가 끝나버렸다(...)

업솔빙 하면 올릴 예정이다.