Codeforces Round #809 (Div. 2)

오렌지 복귀

A. Another String Minimization Problem (0:04, +)

그리디하게 잘 바꿔주면 된다. 평소 A보다는 살짝 어려웠던 듯

 

B. Making Towers (0:13, +)

각 칸 사이에 짝수 개의 원소가 있어야 = 인덱스의 홀짝성이 계속 바뀌어야 탑을 쌓을 수 있다. 이를 바탕으로 잘 구현해주면 된다. 별로 맘에 드는 문제는 아니었다.

 

C. Qpwoeirut And The City (0:22, +)

원소가 홀수개일때는 배치가 결정되지만, 짝수개라면 중간에 한 칸을 띄울 수 있다. 두 경우에 대한 prefix sum을 미리 계산해준 후 어디서 띄울 지를 결정해주면 된다.

 

D1. Chopping Carrots (0:34, +)

MAX를 고정하면 만들 수 있는 수 중 해당 값에 가장 가까운 수를 계속 만들어줄 수 있다. D2는 E 푸느라 깊게 생각해보지 않았다.

 

E. Qpwoeirut and Vertices (1:53, +5)

문제를 처음 보고, 너무 PBS같이 생겨서 바로 PBS 풀이를 구상하기 시작했다. 스몰투라지에 세그를 얹으면 대충 될 것 같아 후딱 짰지만, TLE를 계속 받았다. 시간 복잡도를 계산해보니 로그 세제곱이었던게 문제였다. 그 때, PBS를 쓰는 문제인 크루스칼의 공 문제에 다른 LCA 풀이도 있다는 것을 떠올린 후 풀이를 찾아보았다. 풀이를 보니, 같은 방식으로 트리를 만든 후 LCA 연산을 지원하는 세그만 만들면 될 것 같았다. 30분 정도 남았었기에 시간이 상당히 촉박했지만, 아슬아슬하게 AC를 받을 수 있었다.

 

작년에는 (아직도 이해가 잘 되지 않지만) 블루와 퍼플을 미친듯이 오가던 시절이 있었다. 그리고 올해는 그 경계가 오렌지와 퍼플로만 바뀐 느낌이다. Div. 2만 치면 거의 바로 오렌지로 올라오는데, Div. 1만 치면 바로 퍼플로 내려간다.. 열심히 해야지