ABC 452 후기

✍️ 후기

3번째 앳코더를 마치고 돌아왔습니다!

사실 이번 후기는 좀 늦게 작성해서 올리게 되었는데 말이죠. 그 사유는...

A번부터 다시 보면, 항상 앳코의 A는 매우 쉬웠었죠

이번에도 마찬가지로 단순 출력 문제로 나왔고, 아주 친절하게 1월은 1일이 아니라 7일이다!! 라고 강조까지 해줬네요

B번도 보자마자 예제부터 보고 "아 이거 별 찍기 느낌의 문제다"라는 감이 와서 빠르게 풀었어요.

매번 string으로 별을 신나게 찍어봤던 저로썬 금방 해결하고 넘겼죠.

C번은... 참... 이게 보자마자 지문이 어지러워서 예제랑 같이 보려고 내렸는데 한 5초정도 멍때린거 같아요

문제가 조금 복잡해보였지만, 앳코더의 친절한 예제 덕에 금방 갈피를 잡았고, 이를 기반으로 지문에서 단서들을 찾아내 문제를 해결했어요.

하아... 이제 말하기 싫은 D랑 E번인데요

항상 앳코를 치면서 "오늘도 꼭 D번까지라도 풀어야지"라는 생각으로 앳코를 치곤 하는데..

이번 D는 문제 자체는 이해하기 쉬운데 어떻게 풀어야 할지 고민이더라고요

그래서 일단 버리고 E를 먼저 봤는데, 시그마를 보고선 어 이거 비슷한걸 백준에서 본거 같기도 하고 재밌어 보여서 도전을 해봤었죠

식과 예제를 계속 보면서 어떠한 방식으로 시그마를 정리할 수 있지 않을까? 싶어서 보던 중...

$(i \mod j)$에 대해서 $i \lt j$ 인 경우 항상 이 값은 $i$이므로 시그마에서 $i \lt j$에 대해 $i$를 꺼낼 수 있을것 처럼 보였어요

즉, k에 대해서 $\sum\limits_{j=1}^{M} A_k B_i (k \mod j) = \alpha + A_k\sum\limits_{j=i+1}^{M} B_i$ 꼴로 변형이 가능할거 같았단 말이죠

이러면 연산량이 줄어드는건 맞지만, 사실 큰 문제가 있었는데, $\alpha$를 구하는게 문제죠 이러면.

제한이 $N, M \le 5\times 10^{5}$ 인데 결국 저 꼴로 변경하더라도 $i \gt j$에 대해서는 전부 계산해야하는데, 이도 결국 $O(NM)$꼴이라는게 문제였죠.

이런저런 생각을 하고 D도 보고 하는데... 결국 못알아냈습니다...

그렇다 보니 이번 앳코는 C까지 밖에 못풀었었고요

그래서, 최종적으로는 다음과 같이 레이팅 변동이 되겠습니다

퍼포먼스 변동 : 951 → 938

레이팅 변동 : 240 → 395 (+155)