2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2023 Winter) Open Contest

대회 리뷰/BOJ

2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2023 Winter) Open Contest

hijkl2e 2023. 3. 14. 22:46

www.acmicpc.net

A - 카트라이더: 드리프트

구현

00:04 AC

F - 배너 걸기

sliding window

00:15 AC

K - 시계 맞추기

[1, 720] 범위의 R에 대하여 brute force

00:31 AC

M - 좋은 문자열 만들기

길이가 1 또는 3인 gbs는 존재하지 않는다.

길이가 2인 gbs는 "01"과 "10"이 있으며 이를 만들기 위한 비용은 0 또는 1이다.

이외의 경우에는 항상 2 이하의 비용으로 주어진 문자열을 gbs로 만들 수 있다.

gbs는 다음 패턴 중 하나를 만족한다.

0 0 ... 0 1 * ... * 0 1 ... 1 1
1 1 ... 1 0 * ... * 1 0 ... 0 0
0 0 ... 0 1 ... 1 1
1 1 ... 1 0 ... 0 0

아래 두 가지 패턴은 N이 짝수인 경우에만 가능하다.

최소 비용은 다음과 같이 구할 수 있다.

if S is gbs then

cost = 0

elif S[0] == S[N - 1] && S[1] == S[N - 2] then

cost = 2

else

cost = 1

00:55 AC

J - 치즈

mst 문제로 착각하였다.

00:41 WA

주어지는 정보로 그래프를 구성하면 모든 정점의 차수는 2가 된다(self-loop는 없다고 가정한다).

따라서 동일한 연결 요소에 속하는 정점들은 하나의 사이클에 속하게 된다.

각 사이클마다 인접한 간선 중 최소 하나의 간선을 선택해야 하는데 이때의 최소 비용은 dp로 구할 수 있다.

01:15 RTE

구현 방법에 경미한 오류가 있었다.

01:25 AC

C - 점수 내기

Trie

02:18 TLE

약간의 최적화를 추가한 후 다시 제출하였다.

02:35 AC

1000 ms 제한에 972 ms로 매우 아슬아슬하게 통과하였다.

나의 풀이가 느렸던 이유는 다음과 같다.

첫 번째로 모든 노드에 대하여 maxv[26]과 minv[26]을 정의하였다.

각각 현재 노드의 모든 하위 노드에 대하여 최댓값과 최솟값을 저장하는 배열이다.

배열 대신 일반 변수로 정의하고 현재 노드에서의 최댓값과 최솟값만 관리하도록 하여도 충분하다.

이렇게만 바꾸어도 440 ms로 줄어든다.

두 번째로 동적 메모리를 과도하게 할당하였다.

지금까지 Trie가 필요할 때 구현의 편의성 때문에 동적 메모리 할당을 애용하였다.

최근에 Trie 문제를 몇 개 풀어보면서 알게 되었는데 정적 할당으로 구현하면 속도가 훨씬 빨라진다.

큰 차이가 없을 것 같았는데 입력이 큰 문제에서는 최대 10배까지 차이가 난다.

next 배열 또한 vector 대신 기본 배열로 구현해야 빠르다.

현재 나의 최종 코드는 256 ms에 동작한다.

G - Azber is playing at Biou's house

Azber라는 닉네임이 문제를 어렵게 보이게 만든다.

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

dp[i][j] = 현재 i번 방에 있고 (j < 3 ? "Azber" : "Biou")의 차례일 때 게임의 최종 점수
j % 3 == 0이라면 양방향 이동이 가능하다.
j % 3 == 1이라면 왼쪽 방향으로만 이동이 가능하다.
j % 3 == 2라면 오른쪽 방향으로만 이동이 가능하다.

03:02 AC

L - 따로 걸어가기

잘 모르겠어서 oeis 뒤졌다.

답은 2 * nCr(N + M - 4, N - 2) * nCr(N + M - 3, N - 2) / (N - 1)이다.

03:15 AC

정해는 다음과 같다.

첫 번째 이동에서 토순이가 아래쪽으로 이동한다고 가정하면 토준이는 반드시 오른쪽으로 이동해야 한다.

또한 마지막 이동에서 토순이는 오른쪽으로 그리고 토준이는 아래쪽으로 이동하게 된다.

이제부터 첫 번째 이동과 마지막 이동은 고려하지 않는다.

토순이와 토준이 모두 아래쪽으로 (N - 2)번, 오른쪽으로 (M - 2)번의 이동을 필요로 한다.

중간에 같은 칸에서 만나는 일이 없도록 하려면 어느 시점에서든 다음 조건을 만족해야 한다.

(토순이가 아래쪽으로 이동한 횟수) >= (토준이가 아래쪽으로 이동한 횟수)
(토순이가 오른쪽으로 이동한 횟수) <= (토준이가 오른쪽으로 이동한 횟수)

사실 두 조건은 동일한 조건이기 때문에 하나만 검사해주면 된다.

가능한 이동 방법은 다음 네 가지 중 하나이다.

토순이는 아래쪽으로 이동, 토준이는 오른쪽으로 이동
토순이는 오른쪽으로 이동, 토준이는 아래쪽으로 이동
토순이와 토준이 모두 아래쪽으로 이동
토순이와 토준이 모두 오른쪽으로 이동

여기서 1번 이동과 2번 이동은 마치 괄호 문자열처럼 생각할 수 있다.

3번 이동과 4번 이동은 남은 이동 횟수에 따라 적절하게 추가해주면 된다.

조합과 카탈란 수 그리고 중복 조합을 이용하면 위에서 언급한 식을 유도할 수 있다.

H - 양 가두기

울타리의 최소 개수는 쉽게 구할 수 있지만 넓이를 구하는 과정은 살짝 까다롭다.

단순히 넓이만 최소화하면 울타리의 개수가 늘어나게 된다.

현재 x 좌표에서 y 좌표의 최솟값과 최댓값을 각각 y1과 y2라고 하자.

울타리의 개수를 유지하면서 넓이를 최소화하려면,

y1은 단조 감소하다가 단조 증가하는 형태여야 한다.
y2는 단조 증가하다가 단조 감소하는 형태여야 한다.

multiset을 이용하면 쉽게 구현할 수 있다.

03:37 WA

잘못 구현하면 우리가 끊어지게 되므로 주의해야 한다.

03:45 AC

E - 슬라이딩 퍼즐 마스터 (not solved)

swap 연산만으로 (N × M)!개의 모든 배치를 만드는 문제이다.

먼저 N이 1인 경우만 고려하면 단순히 1차원 배열 형태가 된다.

이때 M = x일 때의 해법을 알고 있다면 이를 이용하여 M = (x + 1)일 때의 해법도 구할 수 있다.

(x + 1)을 가장 오른쪽에 배치한 후 왼쪽으로 한 칸씩 밀다가 다시 오른쪽으로 미는 형태이다.

예시를 보면 이해가 빠를 것이다.

다음은 M이 2일 때의 해법이다.

다음은 M이 3일 때의 해법이다.

1 2 #
1 # 2
# 1 2
# 2 1
2 # 1
2 1 #

다음은 M이 4일 때의 해법이다.

1 2 3 #
1 2 # 3
1 # 2 3
# 1 2 3
# 1 3 2
1 # 3 2
1 3 # 2
1 3 2 #
3 1 2 #
3 1 # 2
3 # 1 2
# 3 1 2
# 3 2 1
3 # 2 1
3 2 # 1
3 2 1 #
2 3 1 #
2 3 # 1
2 # 3 1
# 2 3 1
# 2 1 3
2 # 1 3
2 1 # 3
2 1 3 #
~~UW4VZ~~
~~GQPYQ~~

N이 2 이상인 경우에도 동일한 해법을 적용할 수 있다.

뱀 모양처럼 2차원 배열을 적절히 펴서 1차원 배열로 만들면 된다.

I - UFO in the Sinchon (not solved)

먼저 x 좌표와 y 좌표를 분리하여 생각하자.

ufo가 등장하더라도 사람들의 상대 좌표는 변하지 않음에 주목해야 한다.

다음 연산을 지원하는 Lz Segment Tree를 구현하면 문제를 해결할 수 있다.

구간 [s, e]와 값 val이 주어질 때 [s, e]에 해당하는 모든 원소에 val을 대입하기
구간 [s, e]와 값 val이 주어질 때 [s, e]에 해당하는 모든 원소에 val을 더하기
값 val이 주어질 때 val의 lower_bound 구하기

구현이 많은 문제는 보통 짜증나기 마련인데 이 문제는 나름 재미있게 풀었다.

티스토리