2023 ICPC Sinchon Winter Algorithm Camp Contest Open

2023 ICPC Sinchon Winter Algorithm Camp Contest Open

A - 2023년은 검은 토끼의 해

구현

00:02 AC

 

B - 만다라트 만들기

구현

00:10 AC

 

C - 발머의 피크 이론

two pointer

00:13 AC

 

D - 알파벳 블록

deque and stack

00:17 AC

 

E - 연애 혁명

mst

00:23 AC

 

H - RGB트리

트리 dp

00:41 WA

역추적을 잘못하였다.

00:45 AC

 

J - 가난한 고흐와 붓

고흐가 먼저 시작하는 경우 고흐의 행동을 따라하면 된다.

그렇지 않다면 셀프 루프를 하나 만든 후 고흐의 행동을 따라하면 된다.

01:00 AC

 

I - 천국의 계단

만들 수 있는 단의 개수를 세는 것이 더 간단하다.

높이가 B인 직육면체를 i개 사용한다고 가정하자.

이 경우 높이가 i * B, i * B + A, i * B + 2 * A, ... 인 단을 만들 수 있다.

따라서 만들 수 있는 단의 개수는 ((N - i * B) / A + 1)개이다.

 

서로 다른 i에 대하여 A로 나눈 나머지가 동일하다면 중복 계산을 하게 된다.

따라서 이전 i와 동일한 나머지 값을 갖는 i를 발견하면 계산을 중단해야 한다.

01:09 AC

 

L - 상대음감의 노래찾기

kmp

01:17 AC

 

K - 요가 수업

2-sat

01:30 AC

 

F - 레이저 쏘기

모든 점에 대하여 해당 점으로 향하는 직선을 긋는 풀이를 시도하였다.

00:32 WA

 

처음부터 반사를 이용하는 것이 이득일 수도 있다.

먼저 N개의 점을 (N * K)개의 점으로 분할하자.

각 점으로 향하는 직선을 그은 후 기울기의 빈도를 세주면 된다.

01:39 AC

 

G - 이 게임에서 진정한 탑은 누구인가

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

• dp[i][j][k] = i번 프레임에서 잭스의 체력이 j이고 피오라의 체력이 k일 때,
• 잭스의 이전 행동이 attack이라면 1
• 잭스의 이전 행동이 counter strike라면 2
• 아무런 행동도 하지 않았다면 0
• 불가능한 상황이라면 -1

구현이 많이 복잡한 편이다.

02:24 WA

게임은 300프레임까지 진행되며 300프레임도 포함해야 한다.

02:31 AC

 

M - 함수열과 쿼리

Segment Tree

03:05 AC

 

N - K블록껍질

나머지 문제를 모두 풀었으나 아직 convex hull을 공부하지 않았다.

시간도 많이 남아서 천천히 공부하고 왔다.

 

우선 초기 convex hull을 구성하자.

ch에 포함되지 않는 점을 제거하여도 ch의 크기는 변하지 않는다.

따라서 ch의 크기가 K인 경우 나머지 (N - K)개의 점을 지울 수 있다.

 

이제부터는 ch에 포함되는 각 점을 제거하였을 때의 ch의 크기를 계산하면 된다.

ch에서 반시계 방향으로 연속된 세 점을 각각 A, B, C라고 하자.

그리고 다음과 같은 집합 P를 정의하자.

P = {p | p != B and ccw(A, C, p) < 1}

점 B를 제거하였을 때의 ch의 크기는 ((초기 ch의 크기) + (P로부터 구한 ch의 크기) - 3)과 같다.

 

집합 P는 약간 복잡한 분할 정복을 통하여 구할 수 있다.

05:06 RTE

풀이가 복잡해지니 구현이 조금 꼬였다.

05:35 AC

 

집합 P를 쉽게 구하는 방법을 알아보자.

점 A, B, C의 x 좌표 중 최솟값과 최댓값을 각각 minx와 maxx라고 하자.

P에 속하는 점의 x 좌표는 모두 minx 이상 maxx 이하이다.

초기 convex hull을 구하는 과정에서 모든 점을 정렬하였을 것이다.

따라서 이분 탐색을 통하여 P의 후보를 구할 수 있다.

 

아무리 생각해도 다이아 문제는 아닌 것 같다.

하지만 레이팅 날먹을 위해서 투표는 하지 않았다.

 

끝

끝