선분 트리 병합을 이용한 [FJOI2018] 지도자 그룹 문제 해결
먼저 이 문제는 그리디로 풀기 어려우므로 동적 계획법(DP)을 고려할 수 있습니다.
처음에는 \(dp_{i, j}\)를 \(i\)번 노드를 루트로 할 때 선택된 노드 중 최소 가중치가 \(j\)인 최대 멤버 수로 정의하는 직관적인 방법이 있습니다. 하지만 이 방법은 \(O(n^3)\)의 시간 복잡도를 가집니다. 많은 전이 과정이 동일하므로 비효율적입니다. 더 빠른 전이를 위해 상태를 변 ...
6월 25일 01:53에 게시됨
소수점 버림 조건을 만족하는 쌍 계산 및 비트 연산자 배열 최적화
문제 A: 조건부 쌍 카운팅
분수 i/j의 소수부가 0.5 미만이 되도록 하는 (i, j) 쌍의 개수를 구하는 문제입니다. 수학적으로 변형하면:
i/j - ⌊i/j⌋ < 0.5
양변에 j를 곱하면 i - ⌊i/j⌋·j < 0.5j가 됩니다. 여기서 왼쪽 항은 나머지 연산 i % j와 동일하므로, 최종 조건은 i % j < 0.5j로 단순화됩니다.
구간 패턴 분석
고정된 j에 대해 i가 0부터 n까지 변 ...
5월 27일 21:09에 게시됨