Codeforces Round 939 (Div. 2)

문제풀기

lml 2024. 4. 19. 23:12

간만에 버추얼...

E2 틀린게 너무 아쉽다.

아마 저지 측에서든 Hack에서든 나온 저격코드인 것 같다.

근데 같은 이유로 E1도 틀렸을텐데 E1 데이터가 조금 약한갑다.

A. Nene's Game

제일 작은 a1번째 사람이 쫓겨나지 않기 위해서는 사람 수가 a1보다 적어야 한다.

따라서 답은 min(a1 - 1, 1)

B. Nene and the Card Game

당연히 자기만 가진 카드를 먼저 내는게 이득이다.

이후에는 내가 가진 카드가 깔려 있으면 그 카드를 내면 된다.

따라서 inv[x] = (내가 가진 카드 중 x개인 카드의 수)라고 했을 때,

1) inv[2] > inv[0] : 나만 가진 카드가 더 많기 때문에 inv[2] + inv[1]을 모두 먹을 수 있다.

2) inv[2] <= inv[0] : 나만 가진 카드가 더 적기 때문에 상대가 이후에 내가 낸 카드를 따라올 거고 inv[2]가 최대

시뮬레이션으로도 가능은 할 것 같다.

C. Nene's Magical Matrix

a[i][j] = max(i, j)가 되도록 맞출 수 있다.

방법은 i = n, n - 1, ... 1에 대해서 (1, i, 1, 2, ... n), (2, i, 1, 2, ... n)을 하면 된다.

이거보다 더 큰 방법이 있음은 보이기 상당히 귀찮다.

D. Nene and the Mex Operator

솔직히 N = 18이 제일 큰 힌트였다.

어떤 x개의 연속한 0은 반드시 (x, x, x...)로 만들 수 있다.

-> construction인데 두 부분으로 나눌 수 있다

-> (0, 1, 2, .. .x - 1)로 만드는 것을 perm[x]이라 하자.

-> perm[x + 1] = perm[x] + [1, x + 1] + perm[x] + [1, x + 1]

이제 비트마스킹으로 모든 상황을 생각해보자.

1로 표현되면 이 숫자를 그대로 쓴단 뜻이고, 그것이 아니라면 MEX 계산을 활용한다는 뜻이다

예를 들어 (5, 0, 0, 1, 9)가 있고 비트마스킹이 10001이라면 (5, 3, 3, 3, 9)로 쓰겠다는 의미이다.

모든 비트마스킹 중에서 최댓값을 구하면 된다.

E. Nene vs. Monsters

(0, a, b, c, d, e, f, ...)이 있다고 가정해보자. (단, a, b, c, ... > 0)

a는 절대로 죽지 않는다.

이후의 b, c, d,...은 이전 문자가 생존한 기간에 따라 바뀐다. k를 이전 문자가 생존한 기간이라 하자.

b는 k * a보다 크면 생존할 수 있다. (단, 이때 a는 무조건 생존하여 k = INF이기 때문에 b는 무조건 죽는다)

c는 (b - a) + (b - 2a) + (b - 3a) ... = k * b - k * (k + 1) / 2 * a보다 크면 생존할 수 있다.

d는 (c - (b - a)) + (c - (b - 2a)) + ... = k * c - k * (k + 1) / 2 * b + k * (k + 1) * (k + 2) / 6 * a보다 크면 생존한다.

e는 k * d - k * (k + 1) / 2 * c + k * (k + 1) * (k + 2) / 6 * b - k * (k + 1) * (k + 2) * (k + 3) / 24 * a보다 크면 생존한다.

뭐 저 위에 있는 식을 대충 보면 d는 k^3 / 6에 비례한다는 사실을 알 수 있다.

따라서 숫자들의 범위가 1e9인 시점에서 2000번 정도 그냥 operation을 돌리면 연속한 4개가 0보다 큰 경우가 없다.

그러면 이제 c가 (b - a) + (b - 2a) + (b - 3a) ... = k * b - k * (k + 1) / 2 * a보다만 큰지 확인해주면 된다.

물론 위의 2000번이 조금 불안하다면 d까지 처리하는 코드를 넣어주면 된다.

(300번만 brute-force 돌리고서 d까지 판단해보는 코드도 짜보았다. 더 빠르고 잘 돌아간다!)