구사과

(9/5 23:27 - 다 썼습니다) IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 이동현, 52 / 70 / 65.5, 187.5점, 29등 반딧불, 43 / 60 / 65.5, 168.5점, 33등 박상훈, 43 / 60 / 65.5, 168.5점, 33등 이성호, 43 / 40 / 61, 144점, 56등 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 ..

Algorithmic Engagements 2021. Koszulki 수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다. POI 2019/2020. Najmniejsza wspólna wielokrotność 최소공배수가 $R - L$ 에 대해 지수적으로 커져서 탐색해야 할 쌍이 많지 않다는 사실을 사용합니다. $R - L = 1$ 인 경우, 최소공배수는 그냥 두 수의 곱입니다. $X(X+1) = M$ 을 만족하는 $X$ 가 존재한다면, $X, X + 1$ 을 출력하면 됩니다. 이 경우는 따로 처리합니다. 이차 방정식을 풀거나 이분 탐색을 하시면 됩니다. $R - L \geq 2$ 인 경우, 최소공배수는 적어도 $L(L+1)(L+2) / 2$ 이상입니다. 고로, $L \leq 2 \..

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다. 2차 교육 B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다. D: $S < X..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. 이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료 구조 문제를 고민해 보다가 한번쯤 ..

문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는 크게 Suffix Array, Suffix Tree, Suffix Automaton 이 있는데, 한국에서는 Suffix Array만이 알려져 있는 편이고, 그 외 다른 자료구조..

Codeforces에 올린 글을 보관 목적으로 블로그에도 올립니다. Yesterday I participated in a local contest involving a problem about Monge arrays. I could've wrote some d&c optimization, but I got bored of typing it so I copypasted maroonrk's SMAWK implementation to solve it. Today, I somehow got curious about the actual algorithm, so here it goes. 1. Definition I assume that the reader is aware of the concept o..

A 단순 구현 문제. 물어보는게 복잡해서 약간의 전처리를 했다. 모든 자연수의 진약수의 합을 전처리하면 짧게 할 수 있었다. B 물어보는 게 모든 가방의 평균 중 몇 번째의 어쩌구 같은 아주 복잡한 무언가였다. 특히 가방의 개수가 많으면 사실상 관리가 불가능한 수치이다. 그런데 가방의 개수가 많으면 첫 번째 / 두 번째로 큰 가방만 남겨두고 나머지는 그냥 다 합쳐주면 된다. 그러니까 최적해에서 가방이 많지 않을 거라고 짐작할 수 있고 그 원리에 입각해서 생각하면 된다. 그런 식이었다. 더 정확하게는 기억이 나지 않는다 (...) $(K+1)/2$ 를 올림하고 내림하는 걸 헷갈려서 한번 틀렸다. C 애드혹 문제도 기출 패턴이 있고 웰노운이 있다. 이 문제 와 비슷하게 해결할 수 있다. D 재밌게 풀었다. ..

BOJ 26410. Intersection of Tangents 답은 $(min(x_i), min(y_i))$ 입니다. 이 점에서는 $x$ 축에 평행한 접선과 $y$ 축에 평행한 접선을 그을 수 있습니다. 자명하다고 볼 수도 있고, 이런 저런 복잡한 접근이 정수 점을 잘 못 찾는다는 점에서 착안할 수도 있겠습니다. BOJ 26408. Game 쿼리당 $O(n)$ 먼저, 최적 전략에서 캐릭터는 최대 한번 이동함을 관찰할 수 있습니다. 어떠한 시나리오에서 두 명 이상이 이동을 선택했다고 합시다. 전략에 의해 마지막으로 이동을 선택한 사람이 그 게임의 승자가 됩니다. 그 경우, 그 전에 이동을 선택한 사람은 본인이 결론적으로 게임을 짐에도 불구하고 이동을 선택했기 때문에 가정에 모순입니다. 두 번째로, 승자는..

이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수 있는지 역시 생각해 보면 좋을 것이다. 이 자료구조에 대해서는 예전 코드포스 글을 통해서 한번 들어보고 메모만 해 놓았으..