구사과

CCC 2025 S1. Positioning Peter’s Paintings답은 $2 \min(\max(A, C) + B + D, A + C + \max(B, D))$ 입니다.CCC 2025 S3. Pretty Pens$Q = 0$ 인 경우의 풀이를 먼저 정리합시다. 변호사가 종류를 바꾸지 않을 경우, 각 종류에 대해서 덕의 최댓값을 구한 후 이를 합한 것이 정답이 됩니다. 종류를 바꾸게 된다면, 현재 최댓값으로 선정된 업보 중 덕을 최소화하는 것을 빼서, 선정되지 않은 업보로 교체하는 것이 최적입니다. 즉, 이 때 얻을 수 있는 이득은 (최댓값 중 덕 최솟값) - (최댓값 아닌 업보 중 덕 최댓값) 으로 계산할 수 있습니다. 이 이득 값이 $0$ 이상이면, 최댓값의 합에 이를 더해주면 됩니다. 이렇게 ..

그래프의 최대 독립 집합 문제는, 그래프가 주어졌을 때 최대 크기의 정점 부분집합 $S$를 골라서, $S$ 안에 있는 두 정점을 잇는 간선이 없게끔 하는 문제이다. 이 문제는 NP-complete임이 아주 잘 알려져 있다. 심지어 $O(n^{0.99})$-factor로 approximate할 수 있으면 $\textsf{NP} = \textsf{ZPP}$ 이다 (사실상 $\textsf{P} = \textsf{NP}$ 라는 뜻이다.) 어차피 제대로 못 푸는 문제이니 대신 다음과 같은 그리디 알고리즘을 생각해 볼 수 있다.순열 $\pi$ 를 잡고, 그 순서대로 정점을 순회한다. $\pi$ 는 모든 길이 $n$ 의 순열 중 랜덤하게 샘플.만약 현재 정점과 인접한 정점 중 $S$ 에 있는 정점이 없으면 현재 정점..

최대 차수가 $\Delta$ 인 그래프를 $(\Delta + 1)$ 개의 색으로 색칠하는 문제를 생각해 보자. 이 문제는 정점을 아무 순서로 보면서 남는 색을 배정해 주면 선형 시간에 쉽게 해결할 수 있다. 그러니 간선이 추가되고 삭제되는 쿼리를 넣어보자. 쿼리당 $O(\Delta)$ 시간에 문제를 해결하는 것은 쉽다:간선이 삭제되면 아무것도 하지 않는다.간선이 추가되었고, 만약 두 정점의 색이 다르다면, 한 정점에 대해서 남는 색을 배정해 준다. 남는 색을 찾아줘야 하기 때문에 $O(\Delta)$ 시간이 필요하다.더 빠른 알고리즘은 없을까? 이 문제를 처음 다룬 것은 내가 알기로는 Bhattacharya et al. 2018 이고, 당시에는 expected amortized $O(\log \Delta..

알고리즘을 모델링하는 여러 방법 중 하나는 Decision Tree이다. Decision Tree에서 알고리즘은 입력의 특정 부분을 읽어서 읽은 결과에 따라 YES / NO verdict를 결정하고, 비교 결과에 따라서 두 상태 중 하나로 분기한다. 예를 들어서 비교 정렬에서는 $x_i, x_j$ 를 읽은 다음에, $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정하고, 이 결과에 따라서 두 개의 자식 상태 중 하나로 분기한다.Decision Tree의 최대 깊이는 보통 알고리즘 시간 복잡도의 lower bound를 구성하는데 자주 쓰인다. 비교 정렬에서는 결과 상태가 최소 $n!$ 개이니, 최대 깊이가 적어도 $\log_2 (n!) = O(n \log n)$ 이고, 그래서 모든..

볼리비아 수크레에서 IOI 2025 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.우민규, 100 / 99.33 / 93 / 100 / 82.45 / 100, 574.78점, 2등 (금메달)이유찬, 100 / 58.89 / 86 / 66 / 72.89 / 83, 466.77점, 16등 (금메달)정민찬, 100 / 79.77 / 100 / 66 / 30 / 83, 458.77점, 19등 (금메달)변재우, 39 / 76.25 / 86 / 100 / 64.45 / 83, 448.7점, 24등 (금메달)한국 팀은 Day 2에도 기세를 이어 대단히 좋은 성적을 내었다. 우민규 학생은 Day 1에도 4등의 성적으로 대회를 마무리했는데, Day 2에서는 이를 더 끌어올려 종합 2등의 아주 우수..

(25/08/10: worldmap 풀이 추가)볼리비아 수크레에서 IOI 2025 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.우민규, 100 / 99.33 / 93, 292.33점, 4등정민찬, 100 / 79.77 / 100, 279.77점, 5등이유찬, 100 / 58.89 / 86, 244.89점, 20등변재우, 39 / 76.25 / 86, 201.25점, 60등Day 1 현재, 한국 팀의 성적이 대단히 좋다. 팀 전체적으로 보아도 결과가 좋은 편이고, 우민규 학생과 정민찬 학생은 만점에 대단히 근접한 점수를 받아 개인 성적 면으로도 아주 우수하다. 다음 날 안정적으로만 대회에 임하여도 금메달을 확정할 수 있고, 그보다 더 높은 목표도 노릴 수 있는 수준이다...

BOJ 33365. Password최댓값은 $n$ 입니다. 최솟값은, 비밀번호의 중앙에 비알파벳 문자를 배정한 후, 중앙에서 왼쪽 / 오른쪽으로 세 문자마다 비알파벳 문자를 배정하면 됩니다.BOJ 33324. The Romanian Sieve$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 을 $O(\sqrt n)$ 시간에 계산할 수 있으면 전체 문제를 이분 탐색으로 $O(\sqrt n \log n)$ 시간에 해결할 수 있습니다. 그 방법을 소개합니다.$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 를 계산할 때는, 항상 $\lfloor \frac{n}{i} \rfloor \leq \sqrt n$ 혹은 $i \leq \sqrt n$ 중 하..

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데$|f(x)| \leq g(k)$$Decision(x) = Decision(f(x))$같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:$n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance..

ARC 123 A. Arithmetic Sequence$A_1 + A_3 = 2 \times A_2$ 가 되도록 각 수를 최소한으로 증가시키는 문제입니다. 위 부등식의 두 방향에 따라서 케이스를 나눠 처리하면 됩니다.$A_1 + A_3 \le 2 A_2$ 면 $2A_2 - A_3 - A_1$ 만큼 $A_1$ (혹은 $A_3$) 을 증가시키면 됩니다.$A_1 + A_3 > 2A_2$ 면 일단 $A_1 + A_3$ 이 짝수여야 합니다. 홀수일 경우 둘 중 아무거나 $1$ 만큼 증가시킵시다. 그리고 $A_2$ 를 $(A_1 + A_3) / 2$ 로 증가시키면 됩니다.ARC 123 B. Increasing Triples문제가 연산 을 도입하여 조금 난해하게 쓰여있습니다. 수열 $A$, $B$, $C$ 에서 $A..

2019년 APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한 번 생각해 봐야 할 것 같다.문제를 요약하면 다음과 같다. (원래 문제에서는 트리가 아니라 그래프가 주어지지만, 여기서는 트리라고 가정하고 Hardness를 증명한다. 즉, 문제 상황보다 더 강한 증명이다.)크기 $n$ 의 가중치 있는 트리가 주어졌을 때, 다음 두 연산을 처리하여라:$Update(e, w)$: 간선 $e$ 의 가중치를 $w$ 로 갱신한다.$Query(v, x)$: 정점 $v$ 에서 가중치 $x$ 이..