고민

블로그를 한다고는 계속 생각했지만 어떤걸 써야하나 라는 생각에 미루고 미루다가 오늘에 다다랐다.

결론은 그냥 평소에 하던 ps나 개발일지나 써보는게 어떨까 싶어서 이번에 참가한 코드포스 라운드에 대해 의미있는 첫 포스팅을 하기로 했다.

레이팅 변화

문제 평가와 풀이방식

A

div2 A라고 하기에는 살짝 어려운듯 했다.

MEX라는 사전지식을 이미 알고 있어서 쉽게 풀었던 것 같다.

답 길이가 항상 k가 되고 답이 될수 있는 알파벳은 'a'+n/k까지라는 것을 이용하면 [a, a+n/k) 구간을 탐색 하면서 가장 처음으로 나오는 없는 알파벳이 최적의 MEX가 된다.

이 과정을 k번 반복하면 길이 k인 답을 얻을 수 있다.

시간 복잡도 O(N)

B

상당히 신박한 문제였다. 처음에 도저히 어떻게 접근할 지 몰라서 무지성으로 1부터 숫자를 써내려가기 시작했다.

1 2 3 4 5 6 7 8 9 10 11 12 13

1 1 1 2 2 2 2 2 3 3 3 3 3

N이랑 sqrt(N)을 계속 써내려가다 보니 항상 N%sqrt(N) = 0이 되는 경우는 sqrt(N)이 어떤 숫자이든 3개씩 존재한다는 걸 발견했다.

처음에는 같은 구간을 두 번 세버리는 실수를 해서 WA를 받았지만 바로 고쳐서 AC를 받았다.

이 문제에서 sqrt(N)을 구할 때 C++ builtin sqrt(N)을 사용하게 되면 실수 오차로 인해 틀리는 데이터가 있다고 한다.

나는 실수를 극도로 싫어하는 주의라 binary search로 int sqrt를 구현했고 별 문제가 없었다.

나중에 알게 된 사실인데 정수용 sqrtl(N)이라는 함수가 존재한다고 한다.

시간 복잡도 O(log(lr))

C

상당히 구현이 빡센 case work 문제였다.

일단 규칙을 보고 파악하는데는 큰 어려움이 없었던 것 같다.

직관적으로 생각난 L자 모양에서 빈 부분이 항상 불가능하다를 떠올리고 머리속으로 이동할 수 있는 가능성을 계속 돌려봤다.

L자가 그대로 오른쪽으로 이동하는 것은 항상 가능했고 모든 상황에 대해 빈 부분이 불가능하단 것을 어렴풋이 증명했다.

그래서 사각형을 4개로 잘라 L자의 빈 부분에 있을 경우 불가능 처리를 해줬더니 예제부터 틀린다.

L자가 왼쪽 아래에 붙어있을 경우 이동할 수 있는 구간은 x=1 or y=1 뿐이게 된다.

이러한 예외는 모든 모서리에 대해 적용되므로 총 4가지가 발생한다.

그래서 앞의 일반적인 상황에 대한 로직과 4가지 예외를 처리해줬더니 AC를 받았다.

시간 복잡도 O(1)

D

시간이 1시간정도 남아서 건드려봤으나 예제 3번을 이해하지 못해 끝까지 풀지 못했다.

N제한이 500이라는 점에서 플로이드-와샬을 생각했으나 사실 문제 자체도 이해하기 너무 어려워서 오래 잡고있다가 결국 못풀었다.

대회가 끝나고 정해를 봤는데 나중에 업솔빙 해봐야겠다.

그리고 다음에는 차라리 이렇게 이해가 안되면 E를 보는게 더 낫지 않았을까 싶은 생각도 든다.

총평

아쉬운점도 많았고 오랜만에 한 코드포스라 긴장도 많이 되서 부계로 했지만 나름 괜찮게 한 것 같다.