2022 Sogang Programming Contest Open (Champion)

2022 Sogang Programming Contest Open (Champion)

A - 완전한 수열

소수 판정 + 누적 합

00:03 AC

 

B - DPS

첫 글자 빈도수만 잘 세면 된다.

00:07 AC

 

C - 현대모비스 소프트웨어 아카데미

정렬 + two pointer

00:10 WA

실수로 정렬 코드를 빼먹었다.

00:10 AC

 

D - 수학적인 최소 공통 조상

두 수가 같아질 때까지 더 큰 수를 단계적으로 소인수분해하면 된다.

00:16 AC

 

E - 고양이 목에 리본 달기

dp + Segment Tree

00:22 AC

정해는 최댓값을 두 개 관리하는 것이다.

 

F - 더 어려운 스케줄링

두 개의 deque과 한 개의 set

00:34 AC

 

G - Maximize MEX

관찰 1. x를 만들려면 0부터 (x - 1)까지의 모든 수가 하나씩 필요하다.

관찰 2. 어떤 수든 0 또는 1로 만들 수 있다.

관찰 3. 0부터 순차적으로 만들다가 더 이상 만들 수 없게 되는 수가 정답이 된다.

 

처음 시도하였던 풀이는 다음과 같다.

우선 집합 S를 관리하기 위하여 multiset을 사용한다.

이제 0부터 순차적으로 만들어보면 된다.

x를 만들 때 집합 S에 x가 존재한다면 단순히 삭제하고 넘어간다.

 

x가 존재하지 않는다면 0부터 (x - 1)까지의 모든 수를 만들어야 한다.

이때 필요한 수의 개수는 최대 2^(x - 1)개이다.

따라서 집합 S에서 가장 큰 수를 2^(x - 1)개 제거하여 x를 만든다.

S의 크기가 이보다 작다면 x를 만들 수 없다.

00:47 WA

 

말도 안되는 풀이를 잘도 시도하였다.

잘못된 부분이 크게 두 가지 존재한다.

 

첫 번째로 x를 만들 때 무조건 2^(x - 1)개의 수가 필요한 것은 아니라는 것이다.

집합 S에 0부터 4까지의 수가 각각 하나 이상 존재한다고 가정하자.

이 경우 이미 존재하는 수 5개만을 이용하여 5를 만들 수 있다.

 

두 번째로 무조건 가장 큰 수를 사용하면 안 된다는 것이다.

집합 S가 다음과 같을 때의 정답을 생각해보자.

S = {0 0 1 1 2 2 4}

당장 4가 필요하지 않다고 해서 귀중한 4를 낭비하면 안 된다.

 

그 다음에는 재귀적인 방법을 시도하였다.

함수 solve(x)는 x를 만들기 위하여 필요한 수의 개수를 계산한다.

x가 집합 S에 존재한다면 단순히 삭제하고 넘어간다.

존재하지 않는다면 0부터 (x - 1)까지의 수를 만들도록 solve 함수를 재귀 호출한다.

 

이 재귀적인 풀이는 첫 번째 풀이의 두 가지 문제점을 모두 해결하였다.

먼저 이미 존재하는 수를 우선적으로 사용함으로써 첫 번째 문제점을 해결하였다.

그리고 어떤 수를 사용하는 것이 최적인지 모르므로 실제로 제거하지 않고 필요한 수의 개수만 기록한다.

이로써 두 번째 문제점도 해결하였다.

01:14 TLE

재귀 호출로 인한 시간 복잡도가 문제가 되었다.

 

AC를 받은 마지막 풀이는 다음과 같다.

먼저 multiset 대신 vector를 사용하도록 하였다.

원소의 범위가 작으므로 vector로 map의 역할을 대신할 수 있다.

 

두 번째 풀이에서 문제가 되었던 재귀 호출 또한 완전히 제거하였다.

x를 만들어야 하는 상황을 가정해보자.

A[i] = x를 만들기 위하여 필요한 i의 개수

로 정의하면 x보다 작은 모든 i에 대하여 A[i]의 값은 1이 된다.

 

집합 S에 y가 존재한다면 제거하고 넘어가면 된다.

이때 A[0 .. (y - 1)]의 값은 이전과 동일하다.

y가 존재하지 않는다면 y보다 작은 모든 i에 대하여 A[i]의 값은 A[y]만큼 증가하게 된다.

 

배열 A를 실제로 관리하면 O(N^2)이지만 잘 생각해보면 배열 없이 O(N)에 가능하다.

루프가 한 번 돌 때마다 최소 한 개의 수를 사용하므로 시간 안에 답을 구할 수 있다.

01:41 AC

에디토리얼에서 이분 탐색이 언급되었는데 나는 시간 복잡도 계산을 잘못해서 시도하지 않았다.

 

뒤의 두 문제는 딱 봐도 가망이 없어 보여서 Master Divison으로 넘어갔다.

 

H - 슈퍼 블랙잭 (not solved)

dp 값이 순환한다.

에디토리얼에서는 이분 탐색을 이용하여 초깃값을 수렴시킨다.

모든 문제에 적용 가능한 방법인지는 아직 잘 모르겠다.

이분 탐색의 상한을 구하는 과정도 잘 이해되지는 않는다.

 

I - AND vs OR (not solved)

핵심적인 관찰은 가치가 양수인 연속적인 부분 수열의 개수는 최대 N개라는 것이다.

가치가 양수이려면 a[l]과 a[r] 모두 그 사이의 수보다 커야 한다.

어떤 인덱스 idx에 대하여 a[idx]가 구간 a[l + 1 .. r - 1]에서의 최댓값이라고 하자.

이때 l과 r이 유일하게 결정되므로 고려해야 할 수열의 개수는 최대 N개가 된다.

 

이후 풀이도 간단하지는 않다.

l과 r은 stack으로 구할 수 있다.

그 사이의 or 값은 Segment Tree로 구할 수 있다.

query는 offline으로 처리하며 이 과정에서 추가적으로 Fenwick Tree를 사용한다.

 

잘 생각해보면 Segment Tree 없이 stack으로 or 값을 구할 수 있다.

그런데 Segment Tree 사용 시보다 실행 시간이 더 길어진다.

원인은 잘 모르겠다.

 

끝

끝