Educational Codeforces Round 77

원래 안 하려고 했는데, 너무 오랫동안 코드포스를 안하는 것 같아서 양심의 가책을 느낄 정도까지 되었다. 실제로 꽤나 많은 코포를 할 수 있었는데 걸렀다. 그래서 이번만큼은 하기로 했다. stonejjun이라 크게 부담도 없고 말이다.

A. Heating

두 숫자 n과 m이 주어지면 m을 n개의 숫자로 분리 한 후에 (a1+a2+a3+...an=m) 각 값을 제곱해서 더한 값의 최댓값을 출력하는 문제이다. 테스트케이스 수가 주어진 후, 여러번 주어진다. 
굉장히 느낌이 좋았다. 문제 설명은 보지도 않고 example과 노트만 보고 a1,a2,a3...an이 최대한 비슷해야 한다는 사실을 깨달았다. 예를 들면 (3,10) -> (3,3,4) 가 된다. 00:03. in 20등. 뭔가 되는 날.

B.Obtain Two Zeroes

두 숫자 n과 m이 주어지면 자유롭게 양수 a를 정해 (n-=a,m-=2a)또는 (n-2a,m-a)를 해서 0,0을 만들 수 있는지를 물어보는 문제이다. A와 마찬가지로 테스트케이스 수가 주어진 후, 여러번 주어진다. 
우리는 가능하면 연산을 딱 두 번만 시행하면 된다는 사실을 증명할 수도 있지만 직관으로 바로 알아챘다. 이때 n=a+2b,m=2a+b로 나타내면 (수학에서 맨날 틀리던) 매개변수를 생각하여 a=(2m-n)/3,b=(2n-m)/3 으로 바꿀 수 있다. (2m-n)/3과 (2n-m)/3이 모두 음이 아닌 정수인지를 판단하는 문제.
주사위 6을 굴렸나보다. 오늘이 날이다. 00:06 0틀.

C.Infinite Fence

무한한 길이의 펜스에 칠을 한다. n,m,k가 입력으로 주어진다. n,2n,3n,4n...에는 빨간색을 칠하고, m,2m,3m,4m...에는 파란색을 칠한다. 둘이 겹치는 구간에는 원하는 색을 칠할 수 있다. 이때 색칠을 할 때 k번 연속 같은 색을 사용해서 색칠을 하면 안된다. 
최악의 경우에도 n,m중 작은 색이 k번 같은 색인 경우가 안나오는지를 확인해야 한다. 작은 색을 n이라고 가정하면, 맨처음에 그냥 n(k-1)과 m을 비교했다.  MN   N   NM이런 경우를 고려해주지 못해서 틀렸다. 그래서 +2를 해서 비교하면 될 줄 알았다. +1틀. (2,6)인 경우는 최악의 경우여도 2를 칠하는 칸과 6을 칠하는 칸이 2 떨어져있다. 따라서 gcd를 고려해 주면 된다. n*(k-1)+2*__gcd(n,m) 와 m 을 비교해서 판단한다. 
2틀이 좀 아쉽긴 하지만 00:21. 그럭저럭 나쁘지 않았다.

D.A Game with Traps

이 전까지 너무 잘풀려서 흥분했다. 문제는 읽어보기를 바란다. 설명은 간단하게 하려고 한다. 군인들의 능력치가 있고, 바닥에는 폭탄이 깔려있다. 군인은 폭탄의 능력치 이상일때만 그냥 지나갈 수 있고 아니면 폭탄을 내가 해체해야한다. 나는 무적이다. 그래서 내가 선택한 군인들을 데리고, 내가 미리가서 헤체를 하고 오든 해서 아무튼 주어진 시간안에 건너야 한다. 이때 데리고 갈 수 있는 최대 군인수를 구하는 문제이다.
보자마자 5초컷 파라메트릭 서치. 바로 생각이 났다. O(N)만에 시간안에 그만큼의 군인을 데리고 건너는 것이 가능한지 판별하면 된다. 근데 여기서 뇌절이 왔다. 내가 먼저 가는게 빠른지 먼저 헤체하려면 어디까지 미리 가야하는지를 계산하는 과정에서 뇌절이 왔다. 전체적인 구현방식에서도 그랬다. 다행히 멘탈잡고 마무리했다. 해체하러 갔던 최대 거리와 현재 군대가 있는 위치를 비교해서 그 중 큰 값에서 더 나아가면 된다. 사실 세부적인 구현은 설명하기 너무 어려운 것 같다. 
그런데 중요한점은 내가 실수를 했다. t<=m인데 t<=n이라고 써놓고 10분동안 3틀을 했다. 페널티 +40... 어쩐지 오늘은 운수가 좋더라니... 그래도 잘 마무리? 하였다. 3틀 01:09..

일단 D가 너무 아쉬웠다. n,m 실수만 안했어도 4솔중 거의 탑에 오를 정도로 오늘 정말 느낌이 좋고 잘 풀리는 날이었다. 사실 E를 도전하는게 맞았는데 내가 멘탈이 터져서 이후 제대로 하지를 못했다. 다음부터는 좀 더 침착하게 차분히 해서 이런 좋은 기회를 놓치면 안되겠다.

217등 레이팅 +117  ->1871 다음엔 퍼플 승급전!