PS 일지(2021.10.18)

Bard·2021년 10월 17일

algorithm

PS 일지

목록 보기

2/11

2862. 수학 게임

Platinum 1

문제 분석

N개가 남아있을 떄 최소 몇개를 가져가면 무조건 게임을 승리할 수 있는지 하나씩 세보자.

일단 k개를 선택했다고 하면, 만약 상대가 $(N-k)$ 개에서 $(1 ∼ 2k)$ 만큼 뺐을 때, 무조건 승리할 수 있으면 된다.
즉, 우선 $N-3k \gt 0$ 을 만족하고,
$dp[N-k-1] \leqq 2$ , $dp[N-k-2]\leqq 4$ $\cdots$ $dp[N-3k] \leqq 4k$
를 모두 만족하는 k를 구할 수 있다.

이 사실을 통해 초반 수열을 구해보자.

규칙 찾기

나온 수열은 다음과 같다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
1	2	3	1	5	1	2	8	1	2	3	1	13	1	2	3	1	5	1	2	21	1	2

여기서 일단 dp[i] = i 인 것의 수열을 보면 1,2,3,5,8,13,21.. 이고 피보나치 수열이다.
아닌 경우에는 마지막으로 피보나치 수였던 곳 부터 다음 피보나치 수까지 dp[1~]이 반복된다.

풀이

N이 피보나치 수임을 판별하자.
피보나치 수는 굉장히 빠른 속도로 증가하기 때문에 N이하의 모든 피보나치수를 짧은 시간 안에 찾을 수 있다.
만약 N이 피보나치 수라면 N을 출력한다.
아니라면 N보다 작은 최대의 피보나치수를 N에서 뺀다.
위 과정을 반복한다.

고찰

왜 되는지 잘 모르겠다. 증명을 찾아보려고 했으나 실패했다.. 피보나치수와 왜 연관이 있는걸까.

22850. 초콜릿 쪼개기 게임

Platinum 2

문제 분석

누가 봐도 그런디 문제임을 알 수 있다.
하지만 N,M의 제한이 굉장히 크므로 또 규칙을 찾아야만 할 것 같다.
일단 N,M이 20이하일 때에 대해서 그런디 수를 찾아보자.

규칙 찾기

\begin{matrix} \textcolor{blue}{0} & \textcolor{blue}{0} & 1 & 1 & 2 & \textcolor{blue}{0} & 3 & 1 & 1 & \textcolor{blue}{0} & 3 & 3 & 2 & 2 & 4 & \textcolor{blue}{0} & 5 & 2 \\ \textcolor{blue}{0} & \textcolor{blue}{0} & 1 & 1 & 2 & \textcolor{blue}{0} & 3 & 1 & 1 & \textcolor{blue}{0} & 3 & 3 & 2 & 2 & 4 & \textcolor{blue}{0} & 5 & 2 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 1 \\ \textcolor{blue}{0} & \textcolor{blue}{0} & 1 & 1 & 2 & \textcolor{blue}{0} & 3 & 1 & 1 & \textcolor{blue}{0} & 3 & 3 & 2 & 2 & 4 & \textcolor{blue}{0} & 5 & 2 \\ 3 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 1 & 3 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \textcolor{blue}{0} & \textcolor{blue}{0} & 1 & 1 & 2 & \textcolor{blue}{0} & 3 & 1 & 1 & \textcolor{blue}{0} & 3 & 3 & 2 & 2 & 4 & \textcolor{blue}{0} & 5 & 2 \\ 3 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 1 & 3 & 1 & 1 \\ 3 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 1 & 3 & 1 & 1 \\ 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 1 \\ 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 1 \\ 4 & 4 & 1 & 1 & 1 & 4 & 1 & 1 & 1 & 4 & 1 & 1 & 1 & 1 & 1 & 4 & 1 & 1 \\ \textcolor{blue}{0} & \textcolor{blue}{0} & 1 & 1 & 2 & \textcolor{blue}{0} & 3 & 1 & 1 & \textcolor{blue}{0} & 3 & 3 & 2 & 2 & 4 & \textcolor{blue}{0} & 5 & 2 \\ 5 & 5 & 1 & 1 & 1 & 5 & 1 & 1 & 1 & 5 & 1 & 1 & 1 & 1 & 1 & 5 & 1 & 1 \\ 2 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 1 & 1 \\ \end{matrix}

하.. 잘 모르겠다. 하지만 여기서 알 수 있는 사실은 만약 dp[1][k]가 0인 k의 집합을 S라고 할 때,
S의 임의의 두 원소(중복 가능)를 뽑아 좌표를 구하면 그 곳의 그런디 수는 0임을 알 수 있다.
그리고 한 행에 대해서 좀 더 많이 수를 뽑아 봤다. 그랬더니 놀랍게도.. 첫 두 행을 제외하고 34를 주기로 같은 그런디 수가 나타는 것을 볼 수 있었다..!