NOIP 모의 경연 1 회 후기 및 문제 분석
서론
올해도 역시 AC 자동기 문제에서 고배를 마셨다. 사실 ST3 문제에서 AC 자동기 접근 방식이 매우 자연스럽게 떠올랐고, 절반 정도는 해결했음에도 불구하고 T4 문제로 방향을 틀어 결국 300점 이상의 고득점을 놓치고 말았다. Trie 트리와 실패(Fail) 포인터가 어쩌면 운명적인 조합처럼 느껴지지 않는가? 최종 결과는 100 + 100 + 20 + 0으로 아쉬운 성적으로 마무리 ...
7월 3일 18:18에 게시됨
KDOI-10 컵 냉각 문제 해결
KDOI-10 컵 냉각 문제 - 로그우 플랫폼 (luogu.com.cn)
O(n log n) 시간 복잡도를 가진 알고리즘으로, 각 노드에 대해 최대 및 최소 공기 배출 횟수를 계산합니다. 특정 노드의 최소 횟수가 최대 횟수를 초과하거나 부모 노드 u의 최대 횟수 계산 시 j에서 감소한 값이 허용 범위를 넘으면 냉각 불가능합니다. 그 외 경우는 가능합니다.
최대 횟수 계산은 이분 탐색을 활용 ...
6월 10일 00:28에 게시됨