2023 가지컵
2023 가지컵
www.acmicpc.net
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등상은 가지 인형
끝
끝