[Codeforces] Educational Round 50

http://codeforces.com/contest/1036

 

전형적인 문제를 빠르게 풀어내는 것에는 자신이 있어서 이번 라운드로 오렌지로 복귀하려했으나 시원하게 말아먹었습니다.

 

A - Function Height (Code)

 

최대한 균등하게 뿌려주면 되니 그냥 (n+k-1)을 k로 나눈 몫이 정답입니다.

 

B - Diagonal Working v.2 (Code)

 

생각해보면 답은 K, K-1, K-2 중에 있습니다. case by case로 잘 나눠서 풀면 됩니다.

 

C - Classy Numbers (Code)

 

쉽게 생각하고 코딩으로 뛰어들었다가 시간을 정말 많이 날려먹다가 포기하고, D를 풀고난 후 다시 C로 돌아왔지만 끝날 때 까지 완성을 못했습니다. 거의 1시간 반 정도를 썼는데 너무 슬펐습니다. 지금 다시 생각해보니 nonzero-digit이 3개 이하인게 아니라 zero-digit이 3개 이하인 문제로 착각했던 것 같네요.

 

$10^18$ 이내의 조건을 만족하는 수가 그다지 많지 않아서(100만개 이내) 일단 모든 수를 다 구해놓은 다음에 범위를 잡아서 풀어도 되고, 그냥 범위를 잘 나누어 풀면 됩니다.

 

저는 아래와 같이 해결했습니다.

2105066

(a,b) -> b개의 칸에 non zero를 a개 써야함

2105060~2105066 : (-1, 0) + 5*(-2,0)

2105000~2105059 : (0, 1) + 5*(-1,1)

2100000~2104999 : (1,3) + 4*(0,3)

2000000~2099999 : (2,5) + 0*(1,5)

0000000~1999999 : (3,6) + 1*(2,6)

 

D - Vasya and Arrays (Code)

C에서 말아먹고 D로 넘어왔는데 문제를 읽고 푸는데까지 15분도 안걸렸던 것 같네요. merge sort에서의 merge와 비슷한 느낌으로 제일 왼쪽에서부터 합이 같을 때 까지 두 개의 포인터를 이동시키면서 진행하면 됩니다. 단 두 배열의 합이 같지 않은 경우는 따로 처리를 해주어야 합니다.

 

일단 C번 같은 문제에서 말아먹은 것도 참 안타까운 일이지만, C를 좀 짜다가 너무 오래 걸리겠다 싶으면 빨리 접고 다른 문제로 가던가 했어야하는데 계속 붙잡고 있던게 굉장히 큰 실수였네요. ICPC때 이런 일이 안생기도록 저런 류의 문제도 많이 건들여봐야겠습니다.