Good Bye 2023 Codeforces

https://codeforces.com/contest/1916

 

1/6 기준 싫어요를 4500개 정도 받은 라운드.

여러 이유가 있겠지만 Good bye이기에 참가자가 매우 많았는데, 여러 문제점이 있었다.

 

1. 대장문제인 H가 지나치게 standard한 수학문제 형식으로 나와서 너무 많은 사람에게 풀림

2. G의 MCS에 오류가 있었음. (그로 인해 대회 중에는 AC가 없었고, 대회가 끝나고 재채점)

3. A에서 long long을 사용하지 않을 경우 오버플로가 생기는 테스트 케이스가 pretest에 없어 매우 많은 수의 FST

4. F도 검색이 쉬웠다고 하는데... 글쎄다 이건 잘 모르겠음

5. 문제들 자체가 조금 호불호가 있을 형태이다.

 

아무튼, 문제들이나 살펴보자

 

A. 2023

 

단순하게 b1 * b2 * ... * bn이 2023으로 나누어지는지 확인해보면 된다.

그러면 2023을 나눈 몫과 1들로 k개를 채우면 되기 때문이다.

구현 방식에 따라서 long long을 쓰지 않아도 생존할 수 있지만, 많은 사람이 FST를 먹었다.

 

B. Two Divisors

 

1. 만일 a가 b의 약수라면 (b = ap)

-> x = bq = apq (p != q) 라고 한다면, x의 두 최대 약수는 ap, aq이기에 모순이 생긴다. 따라서 반드시 x = bp = apq

2. 만일 b가 a의 약수가 아니라면

-> 직관적으로 x는 둘의 LCM이 되어야 한다.

 

C. Training Before the Olympiad

 

문제를 보다보면 알겠지만, 짝수인 부분은 절대로 사라지지 않는다.

-> 2A + r1과 2B + r2를 합치면 2(A + B) + 2 * [(r1 + r2) / 2]가 된다.

-> 즉 2A, 2B는 전혀 영향을 받지 않고 r1, r2에 의해서 최종 숫자가 결정된다.

-> 따라서 홀수의 개수만 알고 있으면 된다.

 

나는 여기까지만 진행하고, 홀수의 개수에 따른 최종 점수를 규칙찾기하여 답을 구하였다.

그리디하게 따졌을 때, 대충 cnt / 3과 관련이 있다는 것을 알고 있었기에 규칙은 금방 발견할 수 있었다.

-> 그리디 : Masha는 최대한 1 2개를 합치고 싶으니 1을 2개씩, Olya는 1을 0과 합치고 싶기에 1을 1개씩 줄인다

-> 이걸 발전시키면 찾아낸 규칙을 증명할 수도 있겠지만 굳이?

 

D. Mathematical Problem

 

순수 규칙찾기의 형태.

딱히 수학적인 무언가가 있다고 보기는 어렵다고 생각한다. 

 

내가 찾아낸 구성법

1. 우선 S = [169, 196, 961]로 시작한다.

2. S의 모든 원소에 00을 붙여도 여전히 제곱수이다 (S = [16900, 19600, 96100])

3. 매번 새롭게 2개의 제곱수를 소개한다 -> 90..060..01, 10..060..09 -> (S = [16900, 19600, 96100, 10609, 90601])

이러면 매번 2자리씩 늘리며 2개를 늘릴 수 있다.

 

E. Happy Life in University

 

일단 오일러 투어를 하여 segtree에 순서대로 모든 노드들이 있다고 생각하자.

그러면 (x의 subtree) = [in[x], out[x]) 구간에 속한 모든 y에 대해 segtree에는 diff(x, y) 값이 들어가 있다고 생각하자.

위의 segtree를 가지고 있다면 lca(u, v) = x인 모든 u, v 쌍에 대해서 f(u, v)의 최댓값을 구할 수 있다.

모든 자식에 대해 [in[child], out[child]) 구간의 최댓값 중 제일 큰 2개의 곱을 구하면 된다.

 

그러면 x가 아니라 x의 부모 노드인 p에 대해서 이것이 성립하도록 갱신하려면 어떤 작업을 해야 할까?

-> 1. 우선 p의 모든 후손들에 +1

-> 2. 이후 p의 후손들 중 자신 혹은 조상노드 중에 이미 p와 같은 색이 있던 노드들에 -1

    -> 이것은 조상에 최초로 자신과 같은 색이 등장한 모든 subtree에 -1 처리를 해도 된다.

1은 당연히 N번 이루어지고 2도 최초로 자신과 같은 색이 조상에 등장하는 횟수가 N번 이하로 발생한다.

 

F. Group Division

 

위의 문제에서는 정확히 n1, n2로 나누는게 핵심이다.

처음에는 우선 dfs tree를 생각했다.

그래서 깨작깨작 어떻게 잘 굴리면 될거라 생각했는데 딱히 성과는 없었음. 조금 더 고민했으면 되었을지도...

조금 살펴보다가 H로 튀어갔다.

 

단순하게 생각했으면 될만한 문제였다.

claim) (S1, S2)로 나뉜 상태에서 항상 S2에서 한 개를 골라 (S1 + {x}, S2 - {x})로 나누는게 가능하다

-> T = (S2에 속하면서 S1의 점과 인접한 점들의 집합)

-> T의 원소 중 vertex cut이 아닌게 있다면, 그 원소를 x로 고르면 된다.

-> 모두 vertex cut이라면, 이들 중 제거했을 때 T에 속하는 원소가 없는 component를 만드는 원소 y가 존재한다.

    -> 그럼 이 y는 초기의 그래프에서 제거되었을 때 component를 나누므로 모순

 

시간제한이 꽤나 넉넉해서 편하게 풀 수 있다.

단순하게 S2에 속하는 원소들을 DFS 돌면서 마지막으로 방문한 T의 원소를 x로 고르면 된다.