2023 SCON Open Contest

2023 SCON Open Contest

A - 정보섬의 대중교통

단순 수학

N <= B이므로 A와 B만 비교하면 된다.

이를 인지하지 못해서 조금 오래 걸렸다.

00:04 AC

 

B - 팀명 정하기

정렬

00:07 AC

 

C - 등차수열의 합

등차수열 판별은 쉽다.

수열 B와 C를 구하는 것이 약간 까다로울 수 있는데 아래와 같이 정의하면 된다.

B[i] = A[i], C[i] = 0;

00:10 AC

 

D - 선택 정렬의 이동 거리

다음과 같은 배열 B를 정의하자.

B[i] = 수열 A에서 i의 위치

이제 O(N)에 문제를 해결할 수 있고 잘 구현하기만 하면 된다.

나는 구현이 조금 꼬여서 오래 걸렸다.

00:19 AC

 

E - prlong longf

다음과 같은 점화식을 세울 수 있다.

dp[i] = S[i .. N]에서 가능한 경우의 수

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

dp[i] = dp[i + 1] + (S[i .. (i + 7)] == "longlong" ? dp[i + 8] : 0);

00:22 AC

 

F - 안전한 건설 계획

연결 요소 개수 세기

00:27 AC

 

G - Traveling SCCC President

mst 구하기

00:30 AC

 

H - SCCC 신입 부원 모집하기

굉장히 flow 문제처럼 생겼는데 출제자가 의도한 풀이는 dp라고 한다.

하긴 제한이 수상할 정도로 작았는데 그다지 중요하게 생각하지 않았다.

00:45 WA

번호를 잘못 출력하였다.

00:48 WA

 

오랫동안 반례를 찾지 못하였다.

다행히 찾긴 하였는데 실수하기 쉬운 부분이라 짧게 정리하고자 한다.

우리가 출력해야 하는 정보는 마지막으로 성공한 매칭의 정보이다.

이전 코드에서는 무조건 마지막 매칭의 정보를 출력하도록 하였는데 마지막 매칭이 실패한 매칭일 수도 있다.

다른 문제에서도 비슷한 상황이 가끔씩 등장하니 다음에는 실수하지 않도록 조심하자.

01:03 AC

 

I - 산책과 쿼리

임의의 홀수 사이클에 도달할 수 있는 정점의 개수를 구하는 문제이다.

먼저 N개의 정점을 2N개의 정점으로 분할하자.

예를 들어 정점 x는 (2 * x - 1)과 (2 * x)로 분할할 수 있는데 각 정점은 다음을 의미한다.

• 2 * x - 1: 홀수 시각의 정점 x
• 2 * x: 짝수 시각의 정점 x

이제 query가 들어올 때마다 Union-Find로 정점들을 병합할 것이다.

query (a, b)가 들어오면 (2 * a - 1)과 (2 * b)를 합치고 (2 * b - 1)과 (2 * a)를 합치면 된다.

만약 (2 * a - 1)과 (2 * a)가 동일한 집합에 속한다면 정점 a에서 임의의 홀수 사이클에 도달할 수 있다는 것이다.

02:12 AC

나는 굉장히 오래 걸렸는데 다들 푸는 속도 보니 well-known인 듯 싶다.

 

J - 아이템 (not solved)

아이템을 줍는 과정을 거꾸로 생각해보자.

마지막 아이템을 주운 위치가 x이고 이동 거리는 d라고 가정하자.

이때 가능한 이전 위치 y는 (x + k * d)의 꼴이 된다.

따라서 (x % d == y % d)를 만족하는 모든 위치 y는 이전 위치가 될 수 있다.

 

위의 규칙을 일반화하면 다음과 같아진다.

• i번째 아이템을 주운 위치를 A[i], 마지막 아이템을 주운 위치를 x라고 하자.
• 이때 (A[i] % 2^i == x % 2^i)를 만족하여야 한다.

이제 2차원 배열 B[i][j]를 정의하고 B[i]에서는 (X % 2^i)의 빈도를 세면 된다.

하지만 일반적인 vector로 정의하면 MLE를 받는다.

모든 B[i]에 대하여 원소의 개수는 N개 이하이므로 map을 이용할 수 있다.

하지만 map의 시간 복잡도는 O(log N)이고 전체 시간 복잡도는 O(N log X log N)이 되기 때문에 TLE를 받는다.

 

우리에게는 아직 unordered_map이라는 비장의 무기가 있다.

unordered_map의 평균 시간 복잡도는 O(1)이고 전체 시간 복잡도는 O(N log X)가 된다.

하지만 원인 모를 이유로 20%에서 TLE를 받는다.

unordered_map의 상수가 생각보다 크거나 unordered_map 저격 데이터가 들어 있는 듯 싶다.

 

정해는 Trie인데 대회 중에는 전혀 생각하지 못하였다.

각 노드마다 삽입된 데이터의 개수를 변수 cnt로 관리하도록 하자.

이제 모든 리프 노드에 대하여 루트 노드까지 거슬러 올라가며 답을 계산하면 되는데 이는 재귀적으로 구현할 수 있다.

비트 뒤집기 + 이분 탐색 풀이도 상당히 흥미로우니 관심이 있다면 공부해보자.

 

끝

끝