구사과

이 글 을 보고 작성하였다.BOJ 1763 트리 색칠 이나 AGC 023 F. 01 on Tree 문제는 다음과 같은 최적화 문제로 표현할 수 있다:트리의 모든 topological order $p$ 중에서, \sum_{p(i) 예를 들어 트리 색칠은 $a_i = 1, b_j = C[j]$ 고 01 on Tree는 $a_i = V_i, b_j = 1 - V_j$ 라고 할 수 있다.이 문제를 푸는 알고리즘은 다음과 같다. 만약에 어떤 루트가 아닌 노드의 $b_v / a_v$ 가 트리 전체에서 최대면, 최적해에서 $p$ 와 $v$ 가 인접하게 등장함을 증명할 수 있다. 구체적인 증명은, $[p \ldots w v]$ 의 꼴일 때 $v, w$ 를 바꿔서 손해를 볼 수가 없음. 그래서 저런 최대를 찾은 후 $(..

(9/15 06:58 - Hieroglyphs 만점 풀이를 추가했다.)(9/13 09:44 - 초판 작성)이집트 알렉산드리아에서 IOI 2024 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.김은성, 100 / 58.64 / 59 / 3 / 78 / 64.0, 362.64점, 29등 (금메달)우민규, 100 / 31.40 / 59 / 3 / 100 / 64.0, 357.40점, 33등 (은메달)정희우, 100 / 53.89 / 59 / 3 / 100 / 31.0, 346.89점, 41등 (은메달)정민찬, 100 / 79.64 / 17 / 3 / 78 / 64.0, 341.64점, 48등 (은메달)올해는 학생들의 Day 2 성적이 Day 1 성적보다 약간 낮았고, 결국 금메달 / 은..

이집트 알렉산드리아에서 IOI 2024 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.김은성, 100 / 58.64 / 59, 217.64점, 22등정희우, 100 / 53.89 / 59, 212.89점, 26등정민찬, 100 / 79.64 / 17, 196.64점, 43등우민규, 100 / 31.40 / 59, 190.40점, 52등올해도 작년과 같이 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않다. 또한 그 경계선의 점수 차가 크지 않은 편이다. Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.Day 1의 만점자는 중국의 Kangyang Zhou로 대회 시..

IOI 2018 Day 2 풀이를 작성할 당시 Meetings 문제를 해결하지 못해서, "36점 초과의 풀이는 작성 중입니다" 라고 하고 풀이를 비워두었다. IOI 2024 참관을 위해 알렉산드리아로 가는 비행기에서 드디어 100점 풀이 작성을 완성했다. 원래 글을 끌어올리기에는 시간순 정렬을 너무 깨는 것 같아서 개별 글에 작성한다.Problem길이 $N$의 양의 정수 배열 $A_0, A_1, \cdots A_{N-1}$ 이 있다. $0 \leq L \leq v \leq R $Cost(L, R, v) = \sum_{i = L}^{v-1}{(Max_{j=i}^{v}(A_j))} + \sum_{i = v}^{R}{(Max_{j=v}^{i}(A_j))}$$Q$ 개의 질의가 주어진다. 질의로 $L, R$이 주..

2, 4, 5번 문제의 아이디어를 구상했다.시간 여행각 $i$ 에 대해 $j \le i, A_i - K \le A_j \le A_i$ 를 만족하는 최소 $j$ 를 찾아 그 합을 출력하는 문제이다. $j \le i$ 조건은 함정이다. 어차피 $i$ 가 조건을 만족하기 때문에 무조건 저 조건은 성립한다. 그러면 $A_j$ 값이 특정 구간에 있는 최소 $j$ 를 찾는 문제가 되고, 이는 sliding window minimum 문제이다. $O(N + maxA)$ 나 $O(N \log N)$ 에 해결할 수 있다.공장단순하게는 끝점 작은 순으로 구간을 처리하면서 기존에 넣은 구간과 겹치지 않는 구간을 추가해 주면 된다. 쿼리가 들어올 때, 쿼리로 추가된 구간을 끝점 작은 순으로 정렬하자. Merge sort를 하..

ABC 127 B. Algae주어진 점화식을 계산하면 됩니다. (답은 int32 범위도 넘어가지 않습니다.)PA 2024. Zelki$D[i]$ 를 (조건을 만족하는) 선물 상자 하나를 골랐고, 그 안의 사탕의 무게 합을 $m$ 으로 나눈 나머지가 $i$ 일 때, 가능한 가격 합 최소라고 정의합시다. 원래 문제와의 차이는, 원래 문제에서는 선물 상자를 여럿 고를 수 있다는 점입니다.$D[i]$ 는 동적 계획법을 사용하여 구할 수 있습니다. $DP[x][i]$ 를, 사탕의 색상이 $x$ 이하인 사탕들만 고려하여 무게 합 나머지가 $i$ 가 되게 하는 방법이라고 합시다. $DP[x-1][_]$ 테이블이 채워져 있으면, 색상이 $x$ 인 사탕의 모든 경우를 다 시도하면서 $DP[x][_]$ 테이블을 채울 수 ..

Splay tree 등의 BBST 구현을 여러번 시도해 보았지만 내가 대회에서 직접 짜면 버그가 너무 많아서 보통 피해왔었다. 얼마 전 QOJ를 읽다가 Weight-Balanced Tree라는 Persistent BBST의 굉장히 간단한 구현체를 찾아 이 블로그에 소개한다. 이 구현의 장점은:Rotate 연산을 사용하지 않는다.Rotate 연산은 유도하기 대단히 귀찮아서 보통 암기해야 하고 실수하기 쉽다.사실 이 구현도 Merge에서 암기해야 할 부분이 있는데 Rotate보단 쉬운 거 같다. 그리고 그 부분은 실수를 조금 해도 괜찮다.리프 노드만이 실제 원소에 대응된다. 리프 노드가 아니면 대응되는 원소는 없으며, 왼쪽 자식 / 오른쪽 자식을 모두 가진다. 일반적으로 우리가 사용하는 세그먼트 트리등과 동..

2021.??.?? problem solving이라고 적혀 있는 글이었습니다. 정확히 이 때 이 글을 왜 적었는지는 기억이 안 납니다. 당시에 문제를 몇개 더 풀어서 다른 글과 함께 올리려고 했었는데, 많이 미뤄지기도 했고, 그 문제들은 따로 올리는 게 좋을 것 같아서 그냥 올립니다. 9월까지 알고리즘 글이 최소 5개는 더 올라올 것으로 예상됩니다.AMPPZ 2019 C. Polygon수열 $a_1, a_2, \ldots, a_n$ 을 가지고 볼록 다각형을 만들 수 있을 조건은, 가장 긴 변을 제외한 변들의 길이 합이 가장 긴 변보다 길면 됩니다. 수열을 정렬한 후, 가장 긴 변을 $i$ 번이라고 합시다. 그보다 작은 변들은 합만 특정 수 이상이 되면 되니까, 그냥 전부 골라주면 됩니다. 고로 $1 \l..

Even-Shiloach Algorithm은 Unweighted directed graph $G = (V, E)$ 에 대해서 incremental / decremental SSSP를 빠르게 해결하는 알고리즘이다. Naive하게는 매번 BFS를 해서 $O(m^2)$ 시간에 해결할 수 있는데, 이 알고리즘을 사용하면 이를 $O(nm)$ 으로 최적화할 수 있다. $O(m^2)$ 에 비해서 엄청나게 효율적이진 않지만 분명히 nontrivial한 bound이고, 내가 아는 state-of-the-art method는 전부 다 Near-linear가 아니라 $O(nm)$ 에 훨씬 가까운 바운드이다. 그것도 복잡한 알고리즘들이 대다수. 이 글에서는 원래 Even-Shiloach Algorithm보다 강한 statem..

PA 2016. Shuffle 문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다. $2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다. $2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다. 카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다. ROI 2022 P5. Максимизация выигрыша 입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. ..