제2회 고려대학교 MatKor Cup: 2023 Winter Open Contest

제 2회 고려대학교 MatKor Cup : 2023 Winter Open Contest

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

 

끝

끝