USACO 2023 February Contest > Silver

 

 

https://www.acmicpc.net/group/21869

요즘 그룹을 만들어서 시간을 재고 USACO 셋을 밀고 있다. (가입 신청 환영!!)

첫 연습셋으로 2023 February Contest의 Silver 셋을 돌렸다. 아직 부족한 게 많은 것 같다. ㅠ

 

---

 

27846: Bakery (P4, 수학, 이분 탐색)

 

대충 이분 탐색을 돌리면 되겠다는 생각만 가지고 있었는데, 어떻게 이분 탐색을 돌릴 지 몰라 못 풀었다. 삼분 탐색, 2차원 이분 탐색(...) 등 여러 뻘짓을 했다. 쿠키와 머핀을 굽는 데 필요한 시간의 합을 기준으로 이분 탐색을 돌리면, 놀랍게도 부등식이 잘 풀려서 $O(n)$에 판별 가능한 꼴이 된다! 따라서 시간복잡도 $O(N\log{M})$에 문제를 풀 수 있다. ($M$: $t_C+t_M$의 최댓값)

---

 

27847: Cow-libi (G5, 기하학, 이분 탐색)

 

문제 오독 이슈로 몇 번 틀리고 풀어냈다. Grazing(이게 뭐지..?)을 시간 순으로 정렬하고, 각 cow의 alibi를 잘 끼워 넣을 수 있는지 lower_bound, upper_bound로 잘 판별하면 된다. 유클리드 거리가 아니라 택시 거리로 생각해서 맞왜틀을 많이 했다.

---

 

27848: Moo Route II (P5, 그래프 이론, 그래프 탐색)

 

2024 NYPC Round 2-A에 나왔던 문제와 거의 유사하다. Layover(환승 시간인 듯)라는 귀찮은 조건이 있는데, 이건 그냥 각 flight의  도착 시각에 붙여버리면 된다. (공항 번호, 현재 시각)을 state로 모델링해서, 항공편의 경로에 해당하는 모든 state를 간선으로 이어준 후 bfs/dfs를 돌리면 된다. State가 매우 많기 때문에 필요한 정점만 골라서 저장하고 간선을 이어 주어야 하는데, $i$번 공항에 해당하는 state의 시각이 $j_1, j_2, \cdots, j_n$일 때, 모든 $(j_k, j_{k+1})$ 사이만 간선을 이어 주면 됨을 알 수 있다. 그렇게 초기 상태 (1, 0)에서 bfs/dfs를 돌려 도달할 수 있는 모든 정점을 방문하고, 방문한 정점 중 각 공항에서의 최소 방문 시간을 출력해주면 된다.

별해로 다익스트라를 돌리면서 간선을 지워가는 풀이도 있는 것 같다. https://gubshig.tistory.com/17

 

---