[Codeforces] Educational Codeforces Round 38

 

드디어 보라빛 코더가 됐습니다! 총 7문제였고 A, B <<< C << D < E 인 느낌이었습니다. F, G는 아예 고민을 할 시간이 없어서 ㅎㅎ.. A, B, C, D 4문제를 풀었고 전체를 통틀어 D에서 딱 한 번 틀리고, A / B / C / D 모두 준수한 속도로 풀어내어 전체 88등, Div 2 기준 37등이라는 성적을 거둘 수 있었습니다.

 

A - Word Correction

 

i = 1~ 에 대해, s[i-1], s[i]가 전부 모음일 경우 s[i]를 출력하지 않으면 됩니다. 

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2038/A.cpp

 

B - Run For Your Prize

 

min(a_i - 1, 1000000-a_i)의 최댓값을 출력하면 됩니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2038/B.cpp

 

C - Constructing Tests

 

문제가 잘 이해가 안가 오랜 시간 애를 먹었습니다. 문제에서 결론적으로 요구하는 것은, 주어진 x에 대해 

 

$n^2-(\left \lfloor n/m \right \rfloor)^2=x$ 를 만족하는 n, m을 찾는 것임을 알 수 있습니다. 아래와 같은 방법으로 이러한 n, m을 찾았습니다.

 

i) [n/m]은 n/2 이하이므로 x <= n^2 <= 4/3x 를 만족함을 알 수 있습니다. 이러한 범위에 있는 n^2들을 찾습니다. 이진 탐색으로 찾아도 되고 그냥 선형으로 찾아도 딱히 시간이 오래 걸리지는 않습니다.

 

ii) 이러한 n^2에 대해, n^2 - x가 제곱수인지 확인합니다. 제곱수가 아니면 건너뛰고, 제곱수면 n^2 - x = k^2이라고 합시다.

 

iii) 만약 [n/m] = k를 만족하는 자연수 m이 존재한다면 m = [n/k]일때 성립합니다. n / [n/k] 가 k가 되는지 확인합니다. 만약 된다면 n, [n/k]를 출력합니다. 그렇지 않다면 다음 n에 대해 확인합니다.

 

저 식을 이끌어내는 과정 + 식을 만족하는 n, m을 찾는 과정 둘 다 나름 머리를 써야하는 문제였습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2038/C.cpp

 

D - Buy a Ticket

 

D[i]를 현재 i번째 도시에 사는 사람이 알고있는 가장 효율적인 콘서트장까지의 비용이라고 합시다. 일단 D[i]는 a[i]로 초기화가 가능합니다.(다른 마을의 상태를 모르면 일단 자기 마을에서 관람하면 되니까)

 

a[i]를 priority queue에 전부 집어넣고, 작은 순으로 꺼냅니다. 이전에 꺼낸적이 있는 마을일 경우 그냥 pass, 처음 꺼낸 마을일 경우 그 마을과 접해있는 모든 마을들을 살핍니다. 현재 꺼낸 마을을 v, 접해있는 모든 마을들을 v1 v2 v3, .. 이라고 할 때, a[v_i]를 a_[v]+2*dist(v, v_i)와 비교해 더 작은 것으로 갱신합니다. 그리고 갱신된 마을의 경우 priority queue에 집어넣습니다. Dijkstra와 거의 동일한 방식으로 하면 됩니다. 시간복잡도는 O(V+ElgE)정도일 것 같네요.

 

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2038/D.cpp

 

 

 

각잡고 시작한지 대략 한 달 만에 코드포스 보라색으로 올라왔네요. 일단 단기적인 목표가 보라색 찍기였는데 달성해서 매우 기쁩니다.

 

코드포스를 하면서 영어 문제를 읽어내는 능력과 문제를 빠르고 정확하게 풀어내는 능력이 많이 향상된 것 같습니다. 물론 아직 Div2 E 정도의 난이도는 굉장히 많이 틀리다가 간신히 맞추거나, 아예 착안을 못하거나 하긴 하지만 차차 공부를 거듭하면 나아질 문제로 보입니다.

 

혹시 파랑이나 청록에서 정체된 분이 계시다면 일단 간단한 문제(Div 2 A/B, 경우에 따라 C까지)를 빠르고 정확하게 풀어내는 연습을 기르는게 어떨까 제안을 드려보고 싶습니다. 예를 들어 ACM-ICPC 스타일에서는 4문제를 수많은 WA와 함께 매우 느리게 풀어낸 사람과 3문제를 굉장히 빠르고 정확하게 풀어낸 사람의 등수 차이가 매우 적고, 일반적인 라운드에서는 후자가 전자보다 높은 순위를 차지할 수도 있습니다. 백준과 같은 온라인 저지 사이트에서 그다지 어렵지 않은 문제들(한국정올 초/중등부 문제들)을 많이 풀어보면 도움이 많이 될 것입니다.

 

주황에 도달하기 꽤 오래 걸리겠지만 차분하게 공부를 계속하면서 도전해봐야겠습니다. 이제 Div 2 대회는 참여를 잘 안하게 될테니 코드포스는 조금 뜸해지고 백준을 많이 풀 것 같네요.