[Codeforces] Round #671 (Div.2)

문제 목록 : https://codeforces.com/blog/entry/82743

A. Digit Game

solution

인덱스가 짝수인 자리, 홀수인 자리를 각각 Raze, Breach가 맡고 있다.
마지막에 남은 숫자가 홀수이면 Raze가, 짝수면 Breach가 승리한다.
시작은 Raze부터 하며 선택한 숫자를 없애면 된다.

Raze는 본인이 승리하려면 본인이 선택할 수 있는 것에서 짝수를 먼저 없애야 한다.
거꾸로 Breach는 홀수를 먼저 없애야 한다.
n의 길이가 짝수이면 마지막 차례는 Breach가, 홀수이면 Raze가 된다.
n 길이가 짝수일 땐 Breach가 선택할 수 있는 숫자 중 짝수가 존재해야 승리한다.
반대로 n 길이가 홀수일 땐 Raze가 선택할 수 있는 숫자 중 홀수가 존재해야 승리한다.

B. Stairs

solution

disjoint squares 때문에 조금 애먹었는데.. 이렇게 저렇게 수정해보니 운좋게 답이 나왔다.
TC에서 x의 최댓값이 $10^19$인데 답이 30이라는걸 보고 조금 힌트를 얻은 것 같다.
계단의 가로 길이가 1, 3일 때는 되는데 2일 때는 왜 안되는지 생각해보자.

C. Killjoy

solution

이미 감염된 계정은 rate가 바껴도 여전히 감염된 상태로 유지된다는게 포인트다.
답은 0, 1, 2중 1개만 나올 수 있다.

0일 때는 너무나 당연하게 모든 수가 x와 같으면 된다.
1일 때는 모든 수의 x와의 차들의 합이 0일 때 또는 x와 같은 수가 1개라도 있을 때이다.
전자는 수긍이 가지만 후자는 그렇지 않을 수도 있다. 조금 생각해보니 너무나도 당연했다.
맨 첫줄을 보자. 이미 감염된 계정은 rate 변동에 상관없이 여전히 감염된 상태이다.
때문에 처음부터 감염된 계정이라면 나머지들을 x로 맞추고 생긴 변화값을 감염된 계정에 몰아버려도 모두 감염된 상태가 된다.
2일 때는 바로 위에서 설명한 대로 한 계정에 변화값의 합을 몰아주고 다음 contest에서 남은 계정을 x로 맞춰주면 된다.
즉, 답이 0, 1일 때의 케이스가 아니면 자동으로 답은 2가 된다.

D2. Sage's Birthday (hard version)

solution

정렬해주고 절반으로 쪼개서 큰걸 짝수 자리에, 작은걸 홀수 자리에 놓는다.
그 다음 인접한 값보다 작은 인덱스를 세면 끝난다.