ABC 451 후기

✍️ 후기

2번째 앳코더를 무사히 마쳤습니다!!

이번 앳코는 C번까지는 아주 순조롭게 풀었던거 같네요! C까지 푸는데 14분밖에 안썼다는 사실!!

A는 단순 문자열이 5의 배수인지만 점검해주면 되는 문제였어요. 빠르게 샥샥 풀었죠

B는 단순히 각 부서에서 사람이 얼마나 나가고 들어오는지를 기록하는 문제였어요.

배열 하나 세워주고, 쿼리마다 a번째 부서는 -1, b번째 부서는 +1해서 기록을 해서 풀었어요

C는 사실 처음에는 문제를 보자마자, “어? 스플레이 트리 쓰면 맛있겠는데..?” 싶더라고요 ㅋㅋ!

(앳코 치신 분들이랑 대화 나눴을 당시 다른 분들도 세그나 여러 트리 구조를 떠올렸었다고 했었네요 ㅋㅋ)

뭐 최근에 스플레이 트리를 공부해보고 있어서 그런지 가장 먼저 생각나더군요. 하 지 만

당연히 스플레이 트리는 오버킬이고 더 간단한 방법이 있어서 그걸로 해결했어요.

바로 std::multiset!

내장으로 lower_bound, upper_bound가 있고 각 값이 정렬되어 있는 구조여서 이를 이용해서 쉽게 해결했어요

그리고… C까지만 보여준 이유가 그 뒤로는 완전히 멘탈이 나가버렸기 때문이죠…

D를 처음에 봤을 땐, 제한이 $10^9$이다 보니깐 “이거는 $O(n)$이겠구나”라는 생각에 사로잡혀서 한참을 고민한거 같아요. 이리저리 생각해보다가… 결국 시간만 버리고 E를 읽어보았죠..

근데 E는 더 이상해요!! 그래프 시각화 사이트 에서 마구 굴려보면서 생각해보는데… 번뜩이는 아이디어가 생각났다가 아니었고 이런식으로 너무 시간을 낭비했어요.

그러다가.. D번 보고, 미리 개수를 세놓고 특정 자리수만 나이브하게 계산하면 되지 않을까…? 라는 생각에서 일단 전처리를 위해 나이브로 계산하고 있었어요.

그런데..? 어..? 나이브로 충분히 돌거 같은거에요. 그래서 일단 즉시 짜보았죠.

네.. 돌더라구요…. 구현중에 여러번 실수를 하긴 했는데 결국 맞아내는데 성공했죠!!

다른 분들도 보니깐 대부분 나이브로 구현했다는 의견이 다수였고, 300 ~ 600ms 정도 들더군요 (저는 560ms)

DFS를 이용하신 분도 있었는데, 이것도 꽤 빠르더라구요!

최종적으로 다음과 같이 레이팅 변동이 되겠습니다!

퍼포먼스 변동 : 932 → 951

레이팅 변동 : 75 → 240 (+165)