1. 학교에 공문이 붙어있어 접할 기회가 있었고
2. 마침 과외 등의 일정과 겹치는 일이 없었기에

가볍게 대회를 치고 왔습니다.

6문제 3시간 셋이었는데, 6문제 ABCDEF 중 A B C D 4문제를 해결하였고, 전체 등수는 32등이었습니다.

특별상 조건은 딱히 의도한 바 없어서 아마 못받을거같기는 합니다. 상 받을 생각 없이 출전했던 대회였고 생각보다 괜찮은 등수를 받아내서 만족하고 있습니다.

A. 생일 파티

의도된 난이도는 브론즈3 정도였다고 합니다

두 수의 합이 K가 되는 두 수를 구하는 문제였으며, N의 범위가 작아서 O($N^2$) 로도 문제를 해결할 수 있습니다.

B. 하냥이를 막아라

여전히 브루트포스를 도입할 수 있습니다.

O($N^4$) 로 문제를 해결 할 수 있으며,
점수가 두배가 되는 다섯 부스를 선택하는데 O($N^2$) 만큼의 시간을 사용하고
점수를 계산하는데 최대 O($N^2$) 시간을 사용합니다.

점수가 두배가 되는 다섯 부스는

리온이 (mx,my) 를 선택했다고 할때
abs(mx-x) + abs(my-y) <= 1이 된다면 다섯 부스 안에 속하게 됩니다.

C. 선분 제거하기

그리디 문제입니다.

1931번: 회의실 배정

Baekjoon Online Judge스타트링크 (Startlink)

boj 1931 회의실 배정과 근본적으로 동일합니다

선분을 <회의실 배정> 문제와 동일하게 구간으로 보고,

구간의 끝 y를 기준으로 정렬한 후 O(N)에 훑어낼 수 있습니다.

처음에 그리디라고 생각하고 대충 긁어봤는데 안풀려서

잠깐 당황했었습니다.

여기서 안절었으면 E에 투입할 시간을 확보했을거같아 아쉽습니다.

D. 팰린드롬 아니야

a와 b로 구성된 문자열을 팰린드롬이 아니게 배치했을때 K번째를 찾습니다.

nCr 조합을 적절히 활용해서 a 문자를 A개, b 문자를 B개 사용할 수 있을 때의 경우의 수를 구할 수 있고,

이들 중 팰린드롬인 경우는 A/2개, B/2개씩 사용해서 길이가 절반인 문자열을 만들고 이를 뒤집어 붙여넣는 경우의 수와 동일합니다.

이제 A개 중 preA개가 사용된, B개 중 preB개가 사용된 경우의 수를 구해준 뒤에,

사전순으로 A가 먼저 와야 한다는 것을 이용,

preA가 1이어서 Axxx 이라는 문자열으로 K번째를 만들어 낼 수 있는지,

혹은 preB가 1이어서 Bxxx이라는 문자열으로 K번째를 만들어 낼 수 있는지 를 판별해 낼 수 있고,

이 과정을 재귀적으로 반복해서 log2(K) 시간에 문제를 해결할 수 있습니다.

후기

대회가 끝나고 스코어보드를 까보면서 놀랐던 점으로

1. D번에 플래티넘4를 의도함
2. 빅고수들이 너무나도 많음
3. 6솔이 없음

사실상 E번은 플래상위~다이아하위 를 예상하고 있었던 터라 많이들 못 풀어내지 않을까 하는 예상을 했는데,

스코어보드 상위 1페이지가 5솔으로 도배되어있는 광경을 보고 좀 경악했습니다.

확실히 아직 고등학생물이 덜빠져서 그런건가 싶기도 합니다.

F번은 그냥 보고 어우 이게뭐야 하면서 도망쳤는데 판단을 잘 한것같습니다. 풀어낸 사람이 아무도 없네요

스코어보드 보면서 일반부/대학생부/고등부 이렇게 스코어보드 분리를 시켜주었다면 조금 더 보기 편했을것 같다는 생각을 했습니다.

추가적으로 제가 고등학생이었을 적에는 시간내에 플래를 풀어내기가 힘들었던 기억이 있는데, 대학오고나서 실력이 늘기는 한거같아서 조금 뿌듯합니다.

전반적으로 어떤 태그를 사용해야 할지 굉장히 노골적으로 알려주고 있는 셋이라는 감상을 받았습니다.

이번 겨울방학에는 본가에 안내려가고 서울에 남아있게 되는데, 필연적으로 게임만하면서 뒹굴거리기보다는 PS하고 코드짜면서 실력을 기르게 되지 싶습니다.

+

블로그 글 쓰면서 확인한 사실인데

특별상 조건인

를 받을수 있을지도 모른다는 생각이 듭니다.

A 정답률이 80%로 딱 떨어지는데

제가 정답률 예측을 할때 모든 문제 뒷자리를 0으로 맞췄었기 때문에

존버를해보겠습니다..!