최근에 못푼 ABC 문제들(저장용)

최근에 ABC하면서 내 골통을 괴롭힌 문제들을 모아놨다

까먹을까봐 여기다 메모해 놓고 천천히 풀려고 함

 

https://atcoder.jp/contests/abc383/tasks/abc383_e

E - Sum of Max Matching

최단거리 처럼 보이는 어떤 그래프 문제 같다

정점의 개수가 20만개고 간선의 개수가 최대 20만개이기 때문에

시간 제한 안에 풀려면 NlogN정도로 풀어야 하는데 그러기 위해선 다익스트라 정도만 활용이 가능함

근데 다익스트라를 N개 정점에 대해 모두 실행할려면 N*Nlog N이니깐 이거 아님. 플로이드와 dp를 활용한 풀이도 공간복잡도와 시간복잡도 문제로 불가능함

더 이상 아이디어가 발전하지 않아서 못풀었다

 

==>> 정렬해놓고 유니온파인드쓰면서 모든 간선을 한번씩 연결해보는?? 그리디

구현 난이도도 높다. 에디토리얼 엄청 안읽힘

그룹에 포함된 멤버의 개수를 카운팅하면서 최소 비용을 구한다? 는게 이해안됨

 

 

https://atcoder.jp/contests/abc382/tasks/abc382_c

C - Kaiten Sushi

N명의 사람과 M개의 스시가 있고

M개 스시 회전초밥이 줄줄이 들어오면~ 가장 앞에 서 있는 사람부터 자기 입맛 레벨 이상의 초밥을 집어먹기 시작한다

그래서, 초밥 기준으로 그 초밥을 선택한 사람(없을수도 있음)의 번호를 출력하면 되는데

N과 M이 20만이기 때문에 역시 NlogN으로 풀어야 하고 문제의 감성을 생각하면 queue 또는 priority queue로 풀린다는 감은 오는데 이게 구현하면서 멘붕이 옴

그리고 예전에도 비슷한 문제에 당했던 기억이 난다(번호는 기억이 안난다)

==>> 영어독해이슈로 문제이해를 잘못했다

 

https://atcoder.jp/contests/abc382/tasks/abc382_e

E - Expansion Packs

확률 어쩌구 하는 문제임 식을 잘 정리하면 풀리는 것 같은데 이런 문제에 내가 약하다

예제 입력이 어떻게 예제 출력으로 바뀌는지도 이해를 못했다. 이런 문제가 앳코더에 주기적으로 등장하니 잘 알아둘 필요가 있다

 

https://atcoder.jp/contests/abc380/tasks/abc380_d

D - Strange Mirroring

이건 자다 깨고 정신없어서 못풀었는데 다시 풀어보면 금방 풀지도 모르겠음

 

https://atcoder.jp/contests/abc379/tasks/abc379_f

F - Buildings 2

스택 아님 세그트리로 풀릴 거 같은데 앳코더 F번 난이도가 어느 정도일까 궁금해서 골라 놨다