티스토리 뷰
Intro
UCPC 2020에 애기븝미쟝은 PS를 첨 해보는 것이예얌☆ 라는 팀으로 출전했습니다.
팀원은 다음과 같습니다.
cheetose님이 예약해주신 안암오거리의 스터디카페에 모여서 예선을 치뤘습니다.
예선 당일 서버가 터지는 바람에 22시간 대회를 하게 됐습니다.
해결한 순서대로 문제에 대한 감상을 적겠습니다.
A (110min,+0) - knon0501
가장 쉬운 문제고 미지수가 두 개인 연립방정식을 푸는 문제입니다.
유일한 정수해가 존재하기 때문에 역행렬을 곱해주면 풀 수 있습니다.
수의 범위가 작아 전탐색을 해도 풀 수 있습니다.
D (110min,+0) - cheetose
두가지 종류의 트리의 개수를 세는 문제입니다.
각각 정점과 간선을 기준으로 세면 쉽습니다.
사실 저는 이 문제를 보고 풀이를 바로 떠올리지 못했는데 반성해야겠습니다.
G (110min,+0) - ryute
문제를 안 읽어봐서 모르겠는데 어렵지 않은 것 같습니다.
H (112min,+0) - ryute
마찬가지로 문제를 안 읽어봤는데 쉬운 문제인 것 같습니다.
여기까지 네 문제가 본선 커트라인인 것 같습니다.
J (166min,+2) - knon0501
다섯 번째로 쉬운 문제입니다.
트리를 잘 구성하고 dfs를 잘 뿌려주면 됩니다.
실제 대회였다면 조금 더 빠르고 정확하게 풀어야 할 것 같습니다.
E (176min,+1) - cheetose
꽤 어려운 문제인 것 같은데 치토스님이 밀어주셨습니다.
이문제가 빨리 밀려서 초반 등수가 꽤 높았습니다.
이 시점에서 저는 B,C,I를 보고 있었는데 막막했습니다.
ryute님은 F를 붙잡고 있었는데 꽤 힘든 상황인 것 같았습니다.
저는 6시 반에 과외가 있어서 일찍 스터디카페를 나왔습니다.
8시 반에 과외가 끝나고
롤챔스를 보면서
다시 문제를 보기 시작했습니다.
C (388min,+3) - cheetose
이런 파싱류의 문제는 처음 접해서 당황스러웠는데 치토스님이 밀어주셨습니다.
확실히 이렇게 잘하는 팀원이 있으니 든든했습니다.
F (454min,+8) - cheetose
TLE를 주의해야 하는 성가신 구현문제라고 합니다.
ryute님이 F에서 맞왜틀을 당하자 cheetose님이 처음부터 새로 짜서 맞췄습니다.
I (717min,+1) - knon0501
특정조건을 만족하는 크기가 각각 $a,b$인 두두등장 트리 두 개를 이어붙여서 같은 조건을 만족하는 크기 $a+b+5$의 두두등장 트리를 만들 수 있습니다.
따라서 $n\leq 13$ 인 경우만 찾아 놓으면 재귀적으로 모든 크기의 두두등장 트리를 만들 수 있습니다.
전탐색 코드를 짜서 찾을까 직접 찾을까 고민했는데 코딩을 하기 귀찮아서 직접 찾았습니다.
그런데 이 과정이 1시간이 넘게 걸렸습니다...
처음에 WA한번을 받아서 cheetose님의 D번 코드에 넣어봤더니 문제점을 금방 찾고 고쳐서 맞았습니다.
B (932min,+3) - knon0501
$b$가 클 때 답은 1-3-5-7-10, 1-3-5-7-9, 2-4-6-8 세 가지 중 하나입니다.
그리고 $k$ 자리수의 숫자에 대해 $k+2$ 로 나눈 나머지가 같은 숫자들끼리는 답이 같습니다.
따라서 $dp[i][j]=i+2$ 로 나눈 나머지가 $j$ 인 $i$ 자리수 숫자에 해당하는 답으로 정의하면 $O(b^2)$ 의 전처리 시간과 $O(T\cdot \log b)$ 의 쿼리 처리시간으로 해결 가능합니다.
하지만 $b\leq 10^6$ 이기 때문에 dp테이블을 잡는 것조차 불가능합니다.
dp테이블을 50*50 정도 그려보았는데 한가지 사실을 확인할 수 있었습니다.
바로 연속한 나머지들끼리 같은 답을 가진다는 것입니다.
그래서 dp테이블을 만드는 대신 세 가지 답에 대한 구간만을 들고 다닐 수 있고 $i$ 번째 구간의 양 끝 지점만을 가지고 $i+1$ 번째 구간을 얻을 수 있습니다.
따라서 $O(b)$ 의 메모리와 $O((b+T)\cdot \log b)$ 의 시간복잡도로 해결할 수 있습니다.