[추석맞이 폴란드 스터디] 180925

진도 겨우겨우 맞추는 탐레프 추하다~

풀이 형식

문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.

문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.

문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.

문제 풀이 : (tmi가 포함된) 문제 풀이.

- 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요.

오늘 푼 문제 (1 / Total 11)

POI96. Agents (Div1C)

---

Spoiler alert!

This section is intentionally left blank.

---

POI96. Agents

Tag : SCC, Topological Sort

왜 \(n\)은 3000일까?

note) 디스크립션에 중대한 오타가 있다. 출력이 NIE일 경우, 매수할 수 없는 요원 중 인덱스가 제일 작은 녀석을 출력해야 한다. 역시 ko_osaga님이 지적해 둔 상태.

그래프 문제에 약하기 때문에 전형적인 알고리즘 이외에는 떠올릴 줄 모른다. 다행히도, 이 문제는 전형적인 SCC로 풀릴 것 같아서 시도해 보기로 했다.

다만 로직 설계에서 정신줄 놓고 풀다간 말리기 쉬운 문제다. 당장 코드 짜다가 로직을 3번 정도 수정했다... 새벽에 풀기엔 정말 별로인 문제거나, 아직 내가 그래프 다루기가 미숙하거나.

SCC분해를 통해 DAG를 만든다. 그리고 SCC별로 가장 싸게 매수되는 요원의 가격을 가지고 다닌다. 매수할 수 없는 경우 가격은 inf.

이제 침착하게 위상정렬을 하면 된다. 답을 나타내는 변수 ans를 들고 다니자.

이 때 (Indegree가 0인) 현재 SCC를 매수할 수 있다면, 그 SCC에서 도달 가능한 모든 정점을 매수할 수 있다. 이 처리를 어떻게 할까 고민했는데, 그냥 ans에 현재 SCC 비용을 더해주고, adjacent한 모든 SCC의 가격을 0으로 갱신하면 된다.

tmi) 그러다 문득 "엥? 이 SCC를 반드시 사야 해?"라는 바보같은 생각이 들어서 heap을 꺼낼 뻔했다. 당연히 사야 한다. Indegree가 0이라면 다른 정점으로 이 정점을 매수할 수 없다는 뜻이므로.

만약 현재 SCC를 매수할 수 없다면 일단 출력이 NIE 확정이다. 하지만 현재 SCC를 못 산다고 adjacent한 SCC도 살 수 없는 것은 아니므로, 위상정렬을 함부로 terminate해서는 안된다. 그냥 가격 갱신 없이 위상정렬을 쭉 돌아주자. 대신, "이 SCC는 매수할 수 없다"를 마킹해둔다.

출력이 TAK이라면 그냥 ans를 출력.

NIE라면 "매수할 수 없는" SCC의 모든 정점 중 최소 인덱스를 가진 놈을 출력하면 된다.

시간복잡도는 \(O(n+r)\)이고, r조차 8,000이기 때문에 거의 무조건 0ms가 나온다.