Codeforces Round 868 (Div. 2)

문제풀기

lml 2023. 4. 29. 08:17

A. A-characteristic

1과 -1의 개수만 정해지면 ai * aj = 1인 쌍의 개수는 바로 정해진다.

N이 넉넉하니까 모든 1, -1의 개수에 따라서 시도해보면 된다.

B. Sort with step

swap을 아무리 많이 해도 k에 대한 나머지를 바꿀 수는 없다.

따라서 k에 대한 나머지가 2개 이하인 경우만 가능하고 나머지는 불가능하다.

C. Strongly composite

P와 PQ를 제외하면 Strongly composite하다.

a1 * a2 * ... * an = (p1^q1) * (p2^q2) * ... 이라고 가정하자.

그러면 일단은 P를 두 개씩 묶으면 q1/2 + q2/2 + ... 개를 만들 수 있다.

이제 남은 P들은 3개씩 묶으면 된다. 즉 (q1%2 + q2 % 2 + ... ) / 3개를 추가로 만들 수 있고 이게 답이다.

D. Unique palindromes

3개 이후로 더 이상 palindrome을 만들지 않는 방법 : ABC/ABC/ABC/...의 반복

원하는 개수만큼 unique palindrome을 만드는 방법 : ABC/DDDD...D/ABCD/ABCD/EEEE...EE/...

-> 즉 순환시키면 더 이상 palindrome은 만들어지지 않고, 뒤에 새로운 문자를 연결하면 원하는 만큼 생성 가능하다.

-> 만약에 C2 - C1 > X2 - X1이라면 위의 방법은 불가능하다.

Claim) 위의 방법이 불가능하다면 그냥 불가능한 것이다. (즉, 1번에 unique palindrome은 최대 1개씩만 들어난다)

-> 이거 팰린드롬 개수 세는 문제 해봤으면 비슷한 거를 생각해봤을 문제이다.

-> i 중심 팰린드롬, j 중심 팰린드롬이 새롭게 생겨난다면 (i < j), j 중심 팰린드롬을 뒤집은게 2i - j로써 이미 존재한다.

E. Removing graphs

누가봐도 이건 그런디이다.

Grundy_path, Grundy_loop을 계산한다면 답을 구할 수 있을 것이다.

사실 Grundy 숫자를 규칙찾기로 푸는게 맞는거 같다. (생각보다 간단한 규칙이기 때문)

Grundy 구하는 과정을 최적화하려 했는데 그런 짓은 하지 않는게 맞는 것 같다.

Claim) when i >= L + R, Grundy_loop[i] = 0, else Grundy_loop[i] = i / L

1) when i >= L + R

-> 선공이 몇개를 가져가더라도 R개 이상의 path가 남는다.

-> 여기서 L != R 이기 때문에 후공은 그 path의 중앙부를 없애서 서로 같은 두 개의 path를 만들 수 있다.

-> 그러면 그 path들은 grundy 값이 같으므로 XOR로 인해 Grundy_loop[i] = 0

2) when i < L + R

-> 우선 Min(i, R)개를 선공이 없애면 이기므로 i >= L이면 양수인 것은 확실하다 : XOR 시키려면 이 정보로는 부족

lemma) grundy_path[i] = i / L when i is in [0, L + R)

-> 귀납법) grundy_path[x] = x / L for x < i라고 가정. (grundy_path[x < L] = 0이므로 초항은 성립)

grundy_path[i] = Mex(grundy_path[x] ^ grundy_path[y]) >= Mex(grundy_path[x]) = i / L (x <= i - L이니 0 ~ (i - L) / L)

grundy_path[x] ^ grundy_path[y] <= grundy_path[x] + grundy_path[y] = x / L + y / L <= (x + y) / L <= (i - L) / L

따라서 Mex 값은 반드시 정확히 i / L이 된다.

따라서 grundy_loop[i] = Mex( grundy_path[x] ) (단, x in [i - R, i - L))

-> 이때 i - R < L이므로 grundy_path[x]로 0 ~ (i - L) / L이 모두 나온다.

-> 따라서 grundy_loop[i] = i / L

F. Random walk