[일반] KOI에서 나오는 알고리즘의 한계는 어디까지임?

[하루룽(ailedear)]

요즘 기출문제 돌리는중에 DP Optimization하고 Heavy-Light Decomposition같은거 쓰는 문제들이 보이던데

어디까지 알아둬야 문제풀때 지장없을지 모르겠어

지금 내가 안 나올 것 같다고 생각하는 게 몇 개 있는데

균형잡힌 이진탐색트리 직접짜기

FFT

KMP, 아호코라식

디닉, MCMF
SCC

이것들은 KOI에 나온 적 없겠지??

[0xrgb(0xrgb)]

기본적으로 IOI를 베이스로 하는 시험이기 때문에 대학 교육과정이 필요한 FFT 같은걸 제외하고는 다 나올 수 있음

[0xrgb(0xrgb)]

정확한 범위는 IOI 실라버스를 참고하면 됨

[하루룽(ailedear)]

ㅇㅎ IOI에서 안나온다하면 여기서도 안나오는거임? 출제요강 찾아봐야겠네 ㄳ

[0xrgb(0xrgb)]

그런데 KOI 기출에 HLD가 나왔다고? 안전한 비상연락망 말하는거면 LCA로도 풀 수 있음

[0xrgb(0xrgb)]

http://koosaga.com/107
이거 참고하면 됨. 괜찮은 아이디어들을 소개하고 있으니 한번쯤 읽어볼만함

[하루룽(ailedear)]

이제 이거보고 오프라인 풀이 짜고온다

[하루룽(ailedear)]

https://www.acmicpc.net/problem/13309
내가말한건 이거였음

[하루룽(ailedear)]

누가 HLD로 풀었다길래 사실 난 안풀어서 잘 모름

[0xrgb(0xrgb)]

저건 HLD 맞는듯

[하루룽(ailedear)]

어렵네; 비상연락망은 실력 더키우고 풀러와야겟다 그때 저거 참고해볼게

[시아닌(kimjg1119)]

트리는 정해가 HLD가 아닌 서브트리를 rank-by-optimization으로 관리해주는 방식이라 HLD가 아니다.

[시아닌(kimjg1119)]

DP optimization은 CHT에 한해서 나온적이 있다. 파발마 ㅗㅗ

[시아닌(kimjg1119)]

플로우랑 접미사배열보다 어려운 문자열 알고리즘은 나오면 양심이 뒤진 것이다. 그러나 O(VE) 킹분갓칭 알고리즘은 나올수 있다

[시아닌(kimjg1119)]

FFT는 교육과정상 나올수가 없고 이제까지 BBST 직접짜야하는 문제는 없었음.

[하루룽(ailedear)]

깔끔하게 다 정리해줬네 ㄱㅅ