2023 가지컵

2023 가지컵

A - 가지 교배

흰색 가지만 가지고 있는 조수가 있는지 확인하면 된다.

대회 당시에는 지문이 조금 이상하였는데 출제자의 의도를 파악해서 풀었다.

00:03 AC

 

B - 가지 산사태

1층은 항상 빗물을 받게 되므로 1층만 확인하면 된다.

00:07 AC

 

C - 하이퍼 가지 따기

xor

00:10 AC

 

E - 가지 사진 찾기

가지 사진의 비율이 절반을 초과하므로 가운데 사진은 항상 가지 사진이다.

가지를 가리키는 이름을 알아낼 수 있으므로 가지 사진 번호의 범위는 이분 탐색으로 찾으면 된다.

00:18 AC

 

G - 슬슬 가지를 먹지 않으면 죽는다

mst

00:22 AC

 

F - 가지 이모지

가능한 gcd 값이 얼마 없다는 믿음을 가지고 set으로 풀이하였다.

00:34 AC

동일한 믿음으로 backtracking 풀이 또한 가능하다.

정해는 무슨 말인지 잘 모르겠다.

 

D - :danceplant:

각 방향별로 먹을 수 있는 양분의 양을 적절히 업데이트하면 누적 합 없이 해결할 수 있다.

구현이 살짝 귀찮다.

00:50 AC

 

I - 가지 밭 게임

이분 탐색 + convex hull + 신발끈 공식

01:05 WA

사소한 구현 오류가 있었다.

01:09 AC

 

H - SCP-504

이전 인덱스에서 등장한 문자는 주어지는 단어에 등장하지 않는 문자(예를 들자면 @)로 치환해주자.

정해는 unordered_map인데 대회 중에는 Trie 밖에 생각나지 않았다.

문제 제한 때문에 Trie 풀이는 MLE 발생 가능성이 있으니 주의해야 한다.

02:04 TLE

MLE를 피하려다 TLE를 받았다.

Trie 내에서 이분 탐색을 시도하였다.

02:21 AC

 

대회 종료 후 H번의 Trie 이슈로 적지 않은 말이 오갔다.

예전에 hashing이 정해인 문제를 Aho-Corasick으로 뚫은 경험이 있었는데 H번 풀이에 많은 도움이 되었다.

 

J - 가지 자르기

예제만 보고 항상 4로 나누는 풀이를 시도하였다.

01:21 WA

N각형의 넓이는 항상 f(N)배 감소한다고 가정하고 f(N)을 구해보았다.

01:49 WA

예제를 몇 개 만들어 보니 위의 가정이 잘못되었음을 알 수 있었다.

점의 개수가 동일하더라도 각 점의 좌표에 따라서 넓이가 감소하는 정도는 상이하였다.

 

가지를 K번 자른 후 각 점의 좌표는 초기 좌표의 선형 결합으로 표현할 수 있음을 발견하였다.

이제 행렬 곱셈으로 처리하면 된다.

02:59 TLE

N의 최댓값이 1000이라서 O(N^3 log K) 풀이는 TLE를 받는다.

아무리 생각해도 O(N^3)보다 빠르게 행렬 곱셈을 하는 방법은 보이지 않았다.

 

행렬의 i번째 행은 0번째 행을 i번 shift한 것과 동일하다는 사실을 발견하였다.

따라서 0번째 행만 구할 수 있다면 이로부터 나머지 행도 모두 구할 수 있다.

또한 선형 결합의 모양을 관찰해보니 파스칼의 삼각형의 K번째 행과 유사성이 있었다.

이리저리 시도해보다가 O(N^2 log K) 풀이를 완성시킬 수 있었다.

04:04 WA

 

overflow가 발생하는 부분이 많았는데 전부 모듈러 연산으로 대체하였다.

04:10 AC

 

K - 가지 볶음 (not solved)

Pass

 

L - 가지농장 수확하기 (not solved)

Pass

 

가지 인형

1등상은 가지 인형

 

끝

끝