GBS Coding Contest 2022 Open

GBS Coding Contest 2022 Open

A - 성장의 비약 선택권

case work

00:03 AC

 

C1 - 물정수열

그리디하게 최대한 작은 값을 선택하면 된다.

현재 값을 x라고 하면 다음 값은 max(x + 1, minv)가 된다.

00:21 AC

 

B1 - 알프스 케이블카

H의 제한이 작으므로 dp가 가능하다.

00:39 AC

정해는 그리디이다.

모든 a < b < c에 대하여 선분 (a, b), (b, c), (c, a)는 둔각삼각형을 이룬다.

따라서 모든 인접한 산에 대하여 와이어를 설치하는 것이 이득이다.

 

D1 - 그램팬

조건을 만족하는 A와 Z의 개수를 잘 세주면 된다.

00:49 AC

 

D2 - 팬램그

A와 Z의 개수가 모두 i개인 그램팬을 그리디하게 붙이면 된다.

이때 X는 i^2만큼 감소하며 결과 문자열의 길이는 항상 1e5 이하가 된다.

00:54 AC

 

F - XOR Hashing

모든 값의 개수는 동일하므로 어떠한 값이 등장할 확률은 1 / 2^N이 된다.

같은 해시 값이 존재하지 않을 확률을 구하는 것이 더 간편하다.

01:04 AC

 

E - 성향 성장의 비약

이분 탐색을 잘 돌리면 된다.

01:16 AC

 

H - 바벨탑

stack으로 풀이할 수 있다.

그리디하게 가장 무거운 원판을 선택하되 적절히 제거할 수 있도록 만들어야 한다.

02:16 AC

 

G - 원점

기하는 익숙하지 않고 익숙해지고 싶지도 않다.

내가 아는 공식은 원의 넓이 공식밖에 없어서 인터넷 뒤져가면서 공식을 찾았다.

02:38 WA    02:41 WA    02:46 WA    02:46 WA    02:48 WA    02:50 AC

 

WA를 받은 이유는 다음과 같다.

• 이분 탐색 범위에 오류가 있었다.
• 반지름과 지름을 헷갈렸다.
• EPS를 너무 크게 잡았다.

EPS는 항상 1e-9를 사용하였는데 기하 문제에서는 너무 큰 값이었다.

더 작은 값으로 1e-12를 사용하였더니 잘 돌아간다.

 

에디토리얼은 나의 풀이보다 더 간단한데 차이점은 다음과 같다.

나의 풀이에서는 정다각형의 넓이를 한 변의 길이로 변환한다.

에디토리얼에서는 정다각형의 넓이를 외접원의 반지름으로 변환한다.

이렇게 하면 답이 N인 경우를 더 간편하게 판단할 수 있다.

 

또한 나의 풀이에서는 답을 구할 때 이분 탐색을 이용한다.

공식에 sine 함수가 포함되어 있기 때문에 이분 탐색이 필수라고 생각하였다.

에디토리얼에서는 arc sine 함수로 이를 벗기고 이분 탐색 없이 답을 구한다.

역삼각함수는 정말 오랜만에 보는데 앞으로 마주하는 일 없었으면 한다.

 

I - 점프킹

Union-Find로 풀이할 수 있다.

03:07 WA

Union-Find에서 모든 데이터는 루트 노드를 기준으로 관리해야 한다.

03:13 AC

 

J - 진단 0 : 1 (not solved)

A 이상 B 이하의 수 중에서 M진수로 표현하였을 때 0이 아닌 자릿수가 N개인 수의 개수를 구하는 문제이다.

다음과 같은 재귀 함수를 정의할 수 있다.

/* 0 이상 K 이하의 수 중에서 M진수로 표현하였을 때

   전체 D개의 자릿수 중 0이 아닌 자릿수가 N개인 수의 개수를 리턴 */

ll solve(ll K, ll M, ll D, ll N) { // do something }

 

구체적으로는 다음과 같이 구현할 수 있다.

ll solve(ll K, ll M, ll D, ll N) {

    if K == M^D - 1 then

        return C(D, N) * (M - 1)^N

    D = D - 1;

    if K > M^D - 1 then

        return solve(M^D - 1, M, D, N) + (K / M^D - 1) * solve(M^D - 1, M, D, N - 1) + solve(K % M^D, M, D, N - 1);

    else

        return solve(K, M, D, N);

}

dp를 적용하면 속도가 매우 빨라진다.

 

K1 - 소떡소떡 (not solved)

sweeping으로 풀이할 수 있다.

소시지와 가래떡이 번갈아서 나왔는지 판별하는 부분이 까다롭다.

이는 인접한 동일한 음식물쌍의 개수를 관리함으로써 해결할 수 있다.

규칙을 잘 찾아서 구현해주면 된다.

 

K2 - 소떡소떡 2 (not solved)

에디토리얼은 무슨 말인지 이해하기 어려워서 내 마음대로 풀었다.

Segment Tree와 두 개의 set을 관리하면 된다.

Segment Tree에서는 각각의 y 좌표에 있는 음식물의 길이를 관리한다.

각각의 set에서는 소시지 또는 가래떡의 y 좌표를 관리한다.

동일한 음식물이 인접한 경우에는 가장 길이가 긴 음식물을 선택해야 한다.

규칙을 잘 찾아서 구현해주면 된다.

 

B2 - 알프스 케이블카 2 (not solved)

Pass

 

C2 - 물정수열 2 (not solved)

Pass

 

끝

끝