Codeforces Round #727 (Div. 2) A-D 문제 풀이
A. Contest Start (수학)
이 문제는 패턴을 분석하는 문제입니다. 참가자들의 시작 시간이 일정한 간격으로 배치될 때, 각 참가자가 기다려야 하는 평균 시간을 구해야 합니다.
먼저, 한 참가자가 끝날 때까지 기다리는 다른 참가자의 수를 생각해봅시다.
만약 한 참가자의 경기 시간이 \(t\)이고, 다음 참가자와의 시작 시간 차이가 \(x\)라면, 한 참가자가 경기하는 동 ...
7월 26일 14:19에 게시됨
트리 배열을 활용한 효율적인 구간 합 계산
트리 배열(Fenwick Tree 또는 Binary Indexed Tree, BIT)는 동적 배열에서 구간 합과 단일 요소 갱신을 매우 효율적으로 처리할 수 있도록 설계된 자료구조입니다. 이 구조는 O(log n) 시간 내에 전위 합(prefix sum)을 계산하고, 특정 위치의 값을 수정할 수 있어 빈번한 갱신과 질의가 필요한 문제에서 큰 성능 이점을 제공합니다.
기본 원리
트리 배열은 ...
7월 22일 06:38에 게시됨
NOIP 모의 경연 1 회 후기 및 문제 분석
서론
올해도 역시 AC 자동기 문제에서 고배를 마셨다. 사실 ST3 문제에서 AC 자동기 접근 방식이 매우 자연스럽게 떠올랐고, 절반 정도는 해결했음에도 불구하고 T4 문제로 방향을 틀어 결국 300점 이상의 고득점을 놓치고 말았다. Trie 트리와 실패(Fail) 포인터가 어쩌면 운명적인 조합처럼 느껴지지 않는가? 최종 결과는 100 + 100 + 20 + 0으로 아쉬운 성적으로 마무리 ...
7월 3일 18:18에 게시됨