2022 Goricon Open Contest

2022 Goricon Open Contest

A - 미션 도네이션

단순 수학

00:02 AC

 

B - 배찬우는 배열을 좋아해

가상으로 O(1)에 swap할 수 있다.

00:05 AC

 

C - 도미노 무너트리기

정렬

00:08 AC

 

D - 태풍 예보

구현 문제였는데 너무 많이 틀렸다.

00:38 WA

일부 좌표를 잘못 구하였다.

00:44 WA

방향 판별을 잘못 하였다.

00:49 WA

여전히 방향 판별을 잘못 하였고 변수명을 너무 짧게 써서 서로 다른 변수를 혼동하였다.

00:53 AC

결국에는 맞았는데 멘탈이 바사삭 갈려나갔다.

 

여담으로 CCW를 이용하면 방향 판별이 쉬워진다고 한다.

 

E - 현대 모비스 에어 서스펜션

Aho-Corasick이 떠올랐는데 템플릿 코드를 가지고 있지 않았다.

난이도 분포를 고려하였을 때 정해는 Aho-Corasick이 아닐 것이라고 생각하였다.

 

첫 번째로 bitset 풀이가 떠올라서 시도해보았다.

지금까지 ps를 하면서 bitset을 사용한 것은 이번이 처음이다.

01:13 TLE

pragma 붙여서 다시 시도하였다.

01:15 TLE

 

다른 방법이 떠올랐는데 지금 생각하니 정신 나간 방법이었다.

우선 실시간 데이터의 모든 substring을 multiset에 넣는다.

그리고 모든 판단 데이터에 대하여 multiset에 존재하는 해당 데이터의 개수를 센다.

지금 보면 전혀 가망이 없어 보이는 풀이지만 대회에서는 실수하기 마련이다.

이래서 실전 경험이 중요하다고 하나 보다.

01:21 RTE

인덱스 오류를 범하였다.

01:23 TLE

 

다행히 제대로 된 풀이가 떠올랐다.

판단 데이터의 최대 비트 수는 50이므로 long long 타입으로 저장할 수 있다.

모든 판단 데이터를 길이에 따라 각각의 set<long long>에 넣는다.

실시간 데이터의 모든 substring을 검사하는 것은 이전과 동일하다.

이때 문자열로 취급하지 말고 long long 타입처럼 다루면 된다.

01:34 AC

 

D번과 E번에서 시간을 너무 소비하였다.

남은 시간은 90분 정도였는데 아주대학교 대회와 시간이 겹쳐서 실제로 남은 시간은 30분 정도였다.

전략을 바꿔서 아주대학교 대회에 늦참하고 풀 수 있는 문제는 최대한 다 풀어보기로 하였다.

 

G - 현대 모비스 자율 주행 시스템

정직한 bfs 문제였다.

01:54 AC

 

H - 교수님 서운해 잉잉

정직한 편집 거리 dp 문제였다.

02:19 WA

y 좌표를 잘못 구하였다.

02:21 AC

 

남은 문제는 F번과 I번이었다.

F번은 풀이도 떠오르지 않았고 푼 사람도 적었다.

I번은 푼 사람은 F번보다 많았지만 lca 개념을 요구하는 것 같았다.

30분이 남았지만 풀이를 포기하고 아주대학교 대회로 넘어갔다.

 

I - 어지러운 트리 (not solved)

우선 lca 개념을 알고 있어야 한다.

ps 복귀하고 lca를 사용해본 적이 없어서 복습부터 하고 왔다.

예전에는 sparse table로 구현하였는데 hld 구현이 상당히 간편하였다.

 

다음과 같은 배열을 관리한다.

• sz[x] = x를 루트 노드로 하는 서브 트리의 크기
• dp[x] = LCA(a, b) = x를 만족하는 순서쌍 (a, b)의 개수 (a < b)

두 배열 모두 한 번의 dfs로 구할 수 있다.

루트 노드는 아무 노드로 잡아도 무방하다.

 

1번 query는 단순히 현재 루트 노드를 나타내는 변수 r을 변경해주면 된다.

2번 query는 다음과 같이 case work를 해주면 된다.

if x == r then

    ans = (N - 1) + dp[x] + (sz[x] - 1) * (N - sz[x])

else if x == LCA(x, r) then

    u = x에서 r로 가는 단순 경로에서 x의 자식인 노드

    ans = (N - sz[u] - 1) + dp[x] + (sz[x] - sz[u] - 1) * (N - sz[x] - sz[u])

else

    ans = (sz[x] - 1) + dp[x]

 

그림으로 그려보면 이해하기 쉬울 것이다.

lca를 hld로 구현한 경우 u를 구하기가 조금 까다롭다.

hld의 원리를 알고 있다면 나름 쉽게 구할 수 있다.

 

F - 구분구적 (not solved)

풀긴 풀었는데 풀이는 남기지 않겠다.

할많하않

 

끝

끝