2/20 목요일
32451 Cards: 인버젼 카운팅 + 버블 정렬에 대한 성질들을 많이 얻게 된 것 같습니다.
2/21 금요일
32472 Simple Tree Decomposition Problem
2차 선발고사 전날이기 때문에 제가 아는 알고리즘 중에서 구현을 많이 해보지 않은 알고리즘 문제들을 많이 해결했습니다.
2/22 토요일
IOI 대표 학생 2차 선발고사를 봤습니다.
각 문제에서 47.71, 28, 29, 10점을 받아서 2차 7등, 전체 8등을 했습니다. 최종 10등 안에 들었기 때문에 상당히 만족스럽습니다. 제가 긁을 수 있는 문제는 모두 다 긁은 것 같아서 더 만족스럽습니다. 처음반 중에서 1등이기 때문에 목표했던 계속반은 사실상 확정이고 내년 선발고사에서는 더 잘 볼 수 있도록 노력해 보겠습니다. 히히
- 진화 2 -> 각 서브트리에서 순서를 계산해 준 뒤에 머지 소트나 이분 탐색 등으로 합쳐주는 방식으로 했더니 47점 정도를 받았습니다. 전 두 방법을 따로 사용했었는데 머지 소트나 이분 탐색 중에서 횟수가 더 적은 거로 골라서 하면 70점대까지 나온다고 하네요..
- 멋진 구간 -> 각 구간이 멋진 구간인지 확인하는 것은 금광 세그로 $O(log{N})$로 쉽게 판단해 줄 수 있으므로 $N^2$개의 구간을 모두 판별해서 좌표평면 위에 올리고 세그먼트 트리로 각 쿼리를 처리해 줬습니다. $O(N^2 log{N})$이 $N=5000$ 섭테에서 tle가 나길래 열심히 상수를 깎아서 점수를 받았습니다.
- 넘버링 -> 그래프를 잘 묶어서 트리로 묶어준 뒤에 트리DP를 해주면 됩니다. 이거를 BCC라고 부르는 것 같던데 한 번도 풀어본 적이 없다가 오늘 처음으로 했는데 잘 돼서 뿌듯했습니다. 전 트리DP를 걍 하면 되는데 센트로이드 + CHT를 멍청하게 구현했다가 TLE 받고 결국 100점을 못 받았습니다. 넘버링은 끝난 직후에 제 멍청함을 깨닫고 AC 받았습니다.
- 뗏목 제작 -> CHT 처럼 생겨서 기본 서브테스크만 16977번이랑 비슷하게 짜서 먹었습니다. 긁은 사람이 6명도 안 되는데 아무래도 루비같습니다.
선발고사 기운을 받아 앳코더를 쳤으나 아무래도 기운을 선발고사에서 다 썼나봅니다. F 문제를 잘못 읽어서 한번 망하고 G 구현하다가 여러 자잘한 실수로 또 터졌습니다. 옐로 언제가지
2/23 일요일
옐로 how
'PS' 카테고리의 다른 글
| 2025년 3월 첫째 주 PS 일지 (0) | 2025.03.09 |
|---|---|
| 2025년 2월 넷째 주 PS 일지 (0) | 2025.03.03 |
| 2025년 2월 둘째 주 PS 일지 (4) | 2025.02.17 |
| 2025년 2월 첫째 주 PS 일지 (0) | 2025.02.10 |
| 2025년 1월 다섯째 주 PS 일지 (2) | 2025.02.03 |
