Codeforces Round #666 (Div. 2)

B. Power Sequence

https://codeforces.com/contest/1397/problem/B

처음에 너무 난해했다. 모든 경우를 다 하지 않고 어떻게 구할 수 있는지 고민을 많이 했다. 고민을 하던 중에 c가 2만 되더라도 n이 10^5는 고사하고 n이 30만 되도 10^9를 넘어 사실상 c가 1일때만 10^5만큼 해봐야하고 그 이상일 땐 정말 적은 양만 탐색해보면 되는 문제였다.

C. Multiples of Length

https://codeforces.com/contest/1397/problem/C

어떻게 풀어야 할지 감이 안왔다. 정렬 후 세그먼트 트리로 풀 수 있을까 생각해봤는데 그렇게 하더라도 경우의 수가 너무 많았다. 도저히 생각이 안나서 다른사람 코드를 봤는데 너무 간단해서 허무했다. 1~n-1까지 각 값에 n-1을 곱해 더하면 arr[i] * (n-1) + arr[i] 하면 1~n-1까지의 값이 모두 arr[i] * n 이 되고 n~n까지는 구간의 길이가 1이라 무엇이든 곱해도 되니 arr[last] * (n-1) + arr[last] 로 arr[last] * n 을 만든다. 마지막으로 1~n까지에 -1 * arr[i] * n으로 더해주면 모두 0을 만들 수 있었다. 코드포스식 쉬운 문제들은 이런식의 접근을 해야겠다는 생각을 했다.

D. Stoned Game

https://codeforces.com/contest/1397/problem/D

그리디인건 알겠는데 또 감이 안왔다. 백준에 많은 돌 게임 문제가 있었는데 이건 좀 유형이 다르고 DP로 풀 수 있는 문제였다. 다른 사람의 풀이를 보고 감을 잡고 풀 수 있었다. 먼저 가장 간단하게 생각하면 돌 개수 총 합이 홀수개면 T가 이기고 짝수면 HL이 이긴다. 여기서 변수는 T나 HL이 뽑은 게 마지막 남은 pile이어서 돌이 남았더라도 뽑을 수 없게 되면 돌의 개수와 상관없이 그 돌을 점유하고 있던 플레이어가 이긴다. 이러한 상황은 T만 만들 수 있다. 이 상황이 나오려면 가장 큰 pile이 나머지 pile의 모든 합보다 크면 T가 그 pile만 계속 점유하면 이기기 때문에 이 경우를 예외처리하고 이외에는 짝수홀수 경우로 답을 구했다.