오늘의 PS (2) - 220407~08

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 2개, 코포 2개, 구글 코드잼 1A 라운드가 있었는데, 코드잼은 자느라 못쳤고, 앳코더는 (실력적으로) 못 쳤기 때문에 특별히 잘 친 2개의 코드포스 라운드를 정리해보도록 하겠다.

 

Codeforces Round #781 (Div. 2)

 

A. GCD vs LCM (0:00, +)

보자마자 답이 보여서 짜서 냈다. 덕분에 코포하면서 처음으로 500점을 먹을 수 있었다. ㅎㅎ

 

B. Array Cloning Technique (0:05, +)

가장 많이 등장하는 수의 개수를 센 후, 적당히 2배씩 하면서 횟수를 구해주면 된다.

 

C. Tree Infection (0:33, +3)

킹받는 그리디 문제이다. 우선 노드를 Sibling 단위로 묶으면 트리와 관계 없는 모델링을 할 수 있는데, 이 상태에서 크기가 큰 순으로 모든 덩어리에 전염을 시켜준 후, 마무리는 잘 해주면 된다. 나는 이분 탐색을 사용하였다.

 

D. GCD Guess (0:50, +)

뻔한 인터랙티브라고 생각한다. 대충 gcd(x+1,x+3)을 보냈을 때 x의 홀짝성을 판별할 수 있다는 것을 떠올리면 다른 비트들도 쉽게 정할 수 있다.

 

E. MinimizOR (-)

풀었어야 하는 나름 전형적인 유형의 비트 문제인데, 나는 트라이를 안 만들고 PST랑 머지소트트리로 어떻게 하려다가 코딩이 말려서 못 짰다.

 

 

Educational Codeforces Round 126 (Rated for Div. 2)

ㅎㅎㅎ

A. Array Balancing (0:01, +)

바꾸는 것과 안 바꾸는 것을 비교해 매 인덱스마다 더 작은 값을 더해주면 된다.

 

B. Getting Zero (0:07, +)

주어진 수의 각 켜진 비트에 대해 여기까지는 더하고 그 뒤로는 곱하는 횟수를 구해서 가장 작은 값을 출력해주면 된다.

 

C. Water the Trees (0:20, +1)

최댓값을 변화시키지 않는다고 생각하면 적절한 파라메트릭으로 날짜를 구할 수 있는데, 틀렸다. 그래서 최댓값에서 1 더하는거까지 가능하다고 가정한 후 냈더니 맞았다. Proof by AC

 

D. Progressions Covering (0:49, +1)

백준 17353 이랑 비슷하게 생겨서 세그를 박은 사람이 많은 것 같던데, 세그 없이 풀 수 있다. 뒤에서부터 보면서 누적합을 가중치 유무 두 종류로 나누어 잘 관리해주면 \(O(N)\)에 문제를 해결할 수 있다.

 

E. Narrow Components (1:27, +1)

보자마자 세그라는건 알았는데, 대충 짜니까 잘 안되더라. 합쳐질 때의 경우가 좀 많아서 4개 정도의 변수를 관리하는 자료형을 4개 정도의 조건문으로 합쳐주는 금광 세그를 짜니까 맞았다. 금광 세그 최고

 

 

 

생각보다 E를 푼 사람이 없던 까닭에 상당히 높은 등수를 받을 수 있었고, 그 덕에 오렌지 복귀 + 개인 최고 레이팅을 찍을 수 있었다. 진짜 에듀코포에 뭐가 있는 모양인지, 일반 Div.2에서는 한 번도 못한 두자리 (혹은 한자리) 등수를 에듀에서는 5번이나 찍었더라. 앞으로는 Div.2를 Rated로 못 쳐서 아쉬울 따름이다ㅎㅎㅎㅎ 못 쳤으면 좋겠다..