CodeForces Round 941 - Div 1

https://codeforces.com/contest/1965

 

 

Performance Rating : 2000

 

A

가장 작은 값이 1인지 아닌지가 중요해보였다. 가장 작은 수가 1인 경우 선택권이 없지만 1보다 큰 경우는 선택권이 생기기 때문이다. 가장 작은 값이 $x$이고 $x>1$이면 $(x-1)$개 또는 $x$개를 가져감으로써 같은 상황에서 먼저 할 것인지 나중에 할 것인지를 선택할 수 있기 때문에 무조건 이길 것이라고 생각했다. 그러므로 가장 작은 값이 1보다 큰 상황이 먼저 오는 사람이 이길 것이라는 생각이 들었고 가장 작은 값이 계속 1이라면 $n$의 홀짝성에 따라 승패가 결정될 것이라고 생각했다. 하지만 중복된 숫자가 존재하면 이는 한 묶음으로 봐도 되는데 이를 처리하는 과정에서 실수를 하여 2번 WA를 받았다.

 

B

모든 숫자를 다 만들기 위해서는 $2^i$을 활용해야 하는데 이를 활용하여 풀이를 만들 생각을 했다. $x$를 $2^{i+1}-1<k$를 만족하는 가장 큰 $i$라고 하자. $1, 2, \cdots, 2^x, k+1-2^{x+1}$을 답에 넣으면 $1$부터 $k-1$까지 모든 수를 만들 수 있다. 이제 $k$를 제외하고 $k$보다 큰 수를 어떻게 만들지를 고민했다. 답에 $k$, $2k$, $\cdots$, $2^pk$를 넣으면 $(2^{p+1}-1)k$까지 모든 수를 만들 수 있는데 여기서 수들의 값을 잘 조정하여 $k$만 만들 수 없도록 만들 생각을 했다. $k$를 $k+1$과 $3k$로 바꾸는 방법을 생각해 보니 되는 것을 확인하고 제출했다. 

 

C

3개 이상의 같은 숫자가 연속해 있으면 홀짝성을 유지하면서 1개 또는 2개를 바꿀 수 있다는 것을 생각했다. 우선 문자열을 압축해 놓고 앞에서부터, 뒤에서부터 훑으면서 개수가 짝수이고 펠린드롬이면 반을 날려주는 방식으로 풀었다. 펠린드롬임을 판정하는 것은 해싱을 통해 했다. 하지만 계속 test 2에서 틀렸다는 결과를 받았고 5분이 남았을 때 $10110010$이 $10110010\;-\;1010$으로 접힐 수 있다는 것을 깨달았지만 이미 늦었다.

끝난 후 에디토리얼을 보고 업솔빙을 진행했다. 결국 접을 수 있을 때까지 접었을 때 $1010\cdots$ 꼴이 나온다는 것을 관찰하는 것이 중요했다. 이를 관찰하고 나면 답을 구하는 것은 어렵지 않다.