제2회 고려대학교 MatKor Cup: 2023 Winter Open Contest
제 2회 고려대학교 MatKor Cup : 2023 Winter Open Contest
www.acmicpc.net
A - 몇개고?
단순 수학
00:01 AC
B - 선형 회귀는 너무 쉬워 1
수학
00:07 AC
D - 맨해튼에서의 모임
중앙값 찾기
00:16 AC
E - 디지털 XOR
상당히 귀찮은 문제였다.
가능한 조합을 모두 찾아 봐야 하는데 직접 손으로 찾기는 어렵다.
이를 위하여 분석용 프로그램을 별도로 작성하였고 다음과 같은 결과를 얻었다.
- 피연산자의 개수는 3개 혹은 4개이다.
- 피연산자의 개수가 3개인 경우에는 동일한 숫자를 3번 사용하면 된다.
- 예외적으로 8은 {5, 6, 9}로, 9는 {5, 6, 8}로 조합한다.
- 피연산자의 개수가 4개인 경우에는 각 숫자마다 최적이 되는 조합이 존재한다.
- 예외적으로 4와 7은 만들 수 없다.
구체적인 조합 방법은 생략한다.
N에 4 또는 7이 포함된다면 첫 번째 방법만 가능하다.
그렇지 않다면 두 방법을 모두 시도해본 후 최적의 조합을 출력하면 된다.
01:26 AC
C - 카탈란 마스터의 선분 그리기 게임
문제를 잘못 이해해서 많이 헤맸다.
원 위에 점을 찍는다는 표현부터 이해가 되지 않았다.
찍는 위치에 따라 결과가 달라지는데 어떻게 풀라는 것인지 이해할 수가 없었다.
알고 보니 원의 둘레 위에 찍는다는 뜻이라는데 지문이 모호해보인다.
선분을 그릴 때 이미 그려져 있는 다른 선분과 원 내부에서 교차하면 안 된다는 조건이 있다.
나는 이를 잘못 이해해서 한 번 사용한 점은 다시 사용할 수 없다고 이해하였다.
이렇게 이해하면 13034번과 동일한 조건이 되어 어려운 문제가 된다.
00:18 WA 00:44 WA 01:37 WA 01:46 WA
실제로는 한 점을 끝점으로 하는 선분을 여러 개 그릴 수 있다.
따라서 이 문제는 N각형을 (N - 2)개의 삼각형으로 분할하는 문제로 변형할 수 있다.
2 이상의 N에 대하여 그리는 방법과 관계 없이 선분의 개수는 (2N - 3)개로 항상 홀수가 된다.
따라서 N이 2 이상인 경우 답은 0 1이며 그렇지 않으면 답은 1 0이 된다.
02:21 AC
I - 계란을 떨어뜨리면?
어려워 보이지만 값을 여러 개 구해보면 공식이 보인다.
03:00 TLE
nCr을 상수 시간에 구할 수 있도록 전처리가 필요하다.
03:10 AC
J - 계란으로 돈을 벌면?
이전 문제에서 얻은 공식을 잘 정리하면 된다.
03:39 AC
G - 섯섯시싀 저주
Euler line이라는 사전 지식으로 약간 복잡한 공식을 도출할 수 있다.
빠른 계산을 위해서는 식을 적절히 정리하여 단순하게 만들어야 한다.
추가적으로 실수 오차를 방지하기 위하여 long double 타입까지 사용해야 한다.
04:53 AC
F - 헌내기 현철 (not solved)
Euler's theorem을 이용하여 풀이할 수 있다.
임의의 양의 정수 A와 k에 대하여 A^k ≡ A^(k + 10^k) (mod 10^k) 이 성립함을 보일 수 있다.
A^φ(M) ≡ A^2φ(M) (mod M) 이 성립함을 이용하여 풀이할 수도 있다.
H - 오락 고? (not solved)
N자리 이하 수에서 0이 아닌 숫자 K는 (N * 10^(N - 1))번 등장한다.
먼저 위의 공식을 이용하여 정답의 자리수를 결정한다.
이후에도 위의 공식을 이용하여 각 자리마다 차례대로 숫자를 결정해주면 된다.
K - 동우의 마음씨는 착할까 나쁠까 (not solved)
집을 도로 위에 건설할 수 있다는 낚시 조건이 문제를 어렵게 보이게 만든다.
실제로는 마을에 건설하는 것이 항상 최적이다.
단순히 dfs를 돌리면 된다.
L - Fuzzing Mutant Test (not solved)
복잡한 수식 정리
M - DAGame (not solved)
Sprague-Grundy theorem
각 색깔별로 게임판을 분할하는 것이 핵심이다.
N - 페르마의 마지막 정리 (not solved)
Pass
O - 창호의 유학 준비 (not solved)
Pass
P - 재우의 F를 막아라 (not solved)
Pass
끝
끝