[211231] Good Bye, BOJ 2021! 참여 후기

작년에는 사정 상 GoodBye, BOJ 2020! 을 참여하지 못했고,

나중에 연습삼아 풀어본 결과 1솔밖에 못하는 결과를 얻었다.

 

그래서 이번 GoodBye, BOJ 2021!에선 몇솔을 하든 상관없이, G3~2 까지의 문제들은 전부 해결해보는 것을 목표로 응시하였다.

현재 스코어보드가 뜨지 않아 프리징 스코어보드로 대신한다.

프로징 전에 A~D 4솔,

프로징 후에 E를 시도했으나, 구현미스가 나서 5솔하지 못한 채 4솔로 마무리하였다.

결론적으론, 총 4솔로 마무리했다.

패널티가 좀 있기도 하고, E번을 해결하지 못했기 때문에 최종등수는 90등대이지 않을까 싶다.

 

+) 22.01.01. 추가

84등!

확실히 E가 어려웠던 것 같다.

84등의 좋은 성적을 거두었다 ㅎㅎ

 

확실히 1년 전에 비해 많이 성장했음을 느끼는 계기가 된 대회였다 ㅎㅎ

간단하게 문제 별 느낀 점 및 후기를 남겨보겠다.

 

(스코어보드 및 문제가 다 올라오면 추가 및 수정할 예정이다.)

---

A - 2021은 무엇이 특별할까?

 

10000 보다 좀 더 큰 범위까지의 소수를 에라토스테네스 체나, 일반적인 O(N^2) 또는 O(Nsqrt(N))으로 구해주면 되는데,

나는 1e8까지의 소수를 구해주었다ㅋㅋㅋ 

메모리 초과가 안된게 다행이다.

이렇게 해서 4분 쯤에 한번에 AC를 받았다.

 

이 문제를 제외하곤 한번에 AC를 받은 문제가 없다...

---

B - 예쁜 케이크

 

처음에는 i*i<=1e18까지 에라토스테네스 체 + 브루트포스로 돌다가 TLE를 받았다.

그 이후로 딱히 아이디어가 떠오르지 않아 C를 해결한 후에 다시 살펴보다가,

3k+2 꼴의 수는 무조건 TAK인 것을 파악하고 정수론적으로 성질을 계속 살펴봤던 것 같다.

 

조금 살펴본 후에 9의배수도 TAK이 됨을 확인!

나머지는 어떻게 해도 TAK가 안되므로 이대로 제출해서 2번 틀리고 3번째에 AC.

---

C - 성싶당 밀키트

 

처음 읽었을 때는 우선순위큐? 그리디? 인가 했는데 아닌 것 같았고,

쉬운 방법 고민하다가 매개변수탐색으로 이분탐색하면 정렬 O(NlgN)한 후 K개를 제외한 값의 세균 수를 더해주는 과정으로도 시간초과가 나지 않을 복잡도여서 바로 구현에 들어갔다.

 

그런데 이분탐색 범위 최댓값을 1e12로 잡았다가 WA.

이분탐색 범위 최댓값을 1e9로 잡았다가 WA.

맨처음 초기값을 0이 아닌 LNF로 잡았다가 WA.

정말 여러 번의 WA를 받은 후에, 최대 2e9까지의 값이 답으로 가능함을 깨닫고 4번째에 AC를 받았다.

---

D - 횡단보도

그래프 쪽이긴 한데 무슨 풀이인지 몰라서 고민을 좀 했다.

어쨌건 시간에 따른 비용이 존재하는 것이며, 그 비용을 최소화하는 것이기 때문에 dijkstra를 우선적으로 생각했으며, 이유는 모르겠지만 위상정렬도 생각이 났다.

 

일단 dijkstra로 접근했는데, 예상한 그대로가 맞았다.

priority_queue로 O(MlgN)에 해결할 수 있으며,

주의할 점은 다음 next cost를 priority_queue에 집어넣을 때 반복문으로 while(nextCost <= time)과 같이 작성할 경우 시간초과를 받는다.

 

따라서 주기에 따른 mod 성질을 이용해주도록 하자.

이렇게 해서 2번 정도 틀리고 AC를 받았다.

---

E - XOR 기계

E가 D보다 쉽다는 말이 좀 있던데,

난 전혀 그렇게 느끼지 않았다.

 

꽤나 어려웠다. 선형대수학의 필요성을 다시 한 번 느끼고 간다 ㅠㅠ

 

xor을 이용한 문제인데,

maxAi와 N의 값에 따라 (1<<k)-1번 꼴이 답임을 몇 번 테케를 돌려보면 알 수 있다.

이제 dfs로 값들을 출력해주어야 하는데,

구현미스가 중간에 좀 있어서 시간 내에 정답을 제출하지 못했다.

 

E를 못푼게 좀 많이 아쉽지만,

애초에 증명 못하고 proof by test case로 했기 때문에 틀려도 할말없는 문제 ㅎㅎ...

---

F, G는 보지도 않았다.

안보길 잘한게, 정말 어려운 문제들이라 한다.

이건 내가 아는 사람들, 혹은 내적친밀감 있는 학교 인원분들끼리의 랭킹.

이번에는 내가 운이 좋아 성적이 상대적으로 잘 나왔다.

담에는 울학교 분들 모두 더 좋은 성적을 받아

피드백도 서로 해주고 같이 성장할 수 있었음 좋겠다.

 

여담으로 dotorya님이 A, B를 각각 대회 시작 1분, 2분째에 해결하셨던데... 정말 대단하신 것 같다.

 

업솔빙 포함 5문제를 해결했다.

내년 Good Bye BOJ 2022! 에선 플레티넘 문제 일부도 해결할 수 있도록 꾸준히 노력해야겠다~