Processing math: 100%
알고리즘 블로그
article thumbnail
[JOISC 2018 Day 3] Bitaro's Party ★
PS 문제들 2022. 5. 25. 18:13

문제 링크 usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요... 풀 때 사진 참고하세요. 문제 번역 1부터 N까지 높이에 대한 내림차순으로 번호가 매겨진 N개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) M개의 운하는 서로 다른 마을을 단방향으로 연결합니다. i번째 운하(1iM)은 높은 Si에서 낮은 Ei로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다. 비버 Bitaro의 N명의 친구들은 N개의 마을에 살고 있습니다. Bitaro는 Q번의 파티를 열며, 친구들을 초대할 것입니다. j번째 파티에는 \(Y_j..

article thumbnail
[JOISC 2019 Day 1] Examination(시험) ★
PS 문제들 2022. 5. 17. 20:15

문제 링크 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: N3 000,Q3 000 (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 105,Zj=0 (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자료구조들이 있을 것이다. 그렇게 다음의 3가지 풀이가 있다: Merge sort tr..