leejseo의 블로그

BOJ 문제 링크: https://www.acmicpc.net/problem/16287 아는 분의 블로그(링크)에 이 문제에 대한 풀이가 올라온김에 풀어보았다. 해당 블로그에서는 $O(N^2 \log N)$ 풀이를 설명하고 있다. 이 글에서는 $O(N^2 + \max\{A_i\})$ 풀이와 다른 형태의 $O(N^2 \log N)$ 풀이를 설명한다. Problem 서로 다른 $N$개의 정수 $\{A_i\}_{i=1}^{N}$가 주어진다. 이들 중 4개를 골라 합하여 $W$가 될 수 있는지 판단하는 문제이다. $A_i \le 200,000$이고, $N \le 5,000$이다. Solution $A_i + A_j + A_k + A_l = W$인 $i, j, k, l$의 존재성을 찾는 문제인데, 이 문제의 경우..

이번 Codeforces 라운드는 그래도 A~E까지 5개의 문제를 해결했다. 하지만, 여전히 한 문제를 말려서 못푸는건 마찬가지인 것 같다. F번에 대해 $O(Q\sqrt{N} + 2^6 Q)$ 정도의 풀이를 생각했지만, 포함배제 구현 미스로 대회가 끝났고, 너무 복잡하게 생각해서 케이스를 많이 나누었던게 화근인(화끈이 아님) 것 같다. 해결한 문제에 대한 풀이를 간단히 작성하였다. 대회 문제는 다음 링크에서 풀어볼 수 있다. 링크: https://codeforces.com/contest/1207 A. There Are Two Types Of Burgers 비프 패티 버거를 최대 $p$개, 치킨 패티 버거를 최대 $f$개 만들 수 있다. $pf$개의 모든 경우에 대해 따져보면서, 실제로 만들 수 있는지(..

Round #578에서 레이팅이 18 떨어져서 이번에 Div. 2를 쳤다. 놀랍게도 레이팅이 정확히 18 올라서 원래대로 돌아왔다. 사소한 오류 때문에 D를 8번 내서 맞았다는 것이 너무나도 뼈아팠다. 대회 시작 후 1시간 만에 AC 받을 문제를 2시간 가까이 붙들고 있어서 E번을 볼 시간이 없었다. 해결한 문제에 대한 풀이를 작성하도록 하겠다. 링크: https://codeforces.com/contest/1206 Div 2A Choose Two Numbers 총 $O(NM)$개의 $(a_i, b_j)$ 쌍을 직접 확인하면서 $a_i + b_j \in A \cup B$인지 체크해주면 된다. 이대로 구현하면 $O(NM(N+M))$이고, $A$와 $B$의 원소들의 크기가 작음을 이용하면 $O(NM)$에도 ..

PS 하면서 약수의 개수와 관련된 문제를 종종 볼 수 있다. 그래서 글을 작성중이었는데, 마침 NYPC에 이 글의 내용 중 일부를 그대로 쓰면 되는 문제가 나왔다고 한다. 그래서 글을 날렸고, NYPC 예선이 끝난 이제야 업로드한다. 글을 날렸던 만큼 다듬어지지 않았을 수 있다. 나중에 수정할 예정이다. 1. 약수의 개수 구하기 양의 정수 $N$이 주어지고, $N$의 약수의 개수를 구한다고 해보자. $O(\sqrt{N})$ 알고리즘 부터 소개하겠다. 이 알고리즘은 간단하다. $N = xy$로 나타내어 진다고 할 때, $x$와 $y$중 하나는 $\sqrt{N}$ 이하이고, 다른 하나는 $\sqrt{N}$ 이상이다. 따라서, $\sqrt{N}$ 이하의 수들만 봐도 약수의 개수를 구할 수 있다. C++ 구현은..

Note: ${n \choose r} = {}_n C_r$이다. 먼저, 고등학교 미적분 시간에 배우는 내용을 활용하여 명제 몇 가지를 증명하고 가자. Proposition 1. $n \ge 2$인 정수 $n$에 대해 $\int \sin^n x dx = -\frac{1}{n} \cos x \sin^{n-1} x + \frac{n-1}{n} \int \sin^{n-2} x dx$. 증명은 간단한 부분적분을 통해 할 수 있다. Proposition 2. $I_n = \int_0^{2\pi} \sin^n x dx$라 하자. 이 때, 다음이 성립한다: $$I_{2n} = \frac{2n-1}{2n} \frac{2n-3}{2n-2} \cdots \frac{1}{2} \frac{\pi}{2}, \quad I_{2n+..

한국인 두 분(hyunuk, djm03178)께서 주최한 라운드라 직접 응시해봤다. 한동안 PS를 하지 않다가 다시 시작하는 상태라 구현이 느리고 사소한 오류를 잡기 힘든 상태라 레이팅이 떨어질 것 같았지만, 언제까지나 대회 치는걸 미룰 수는 없는 것 아닌가. 어쨌든 대회를 쳤고, A, B, C, E 4개의 문제를 풀었고, D는 사소한 코딩 미스 때문에 맞는 접근으로 WA를 받았고, 훨씬 간편하고 코딩 미스를 방지할 수 있는 구현을 대회 종료 몇 초 후에 떠올렸다는 점에서 너무나도 아쉬움이 크다. 게다가, E에서 해싱을 잘못 짠 것과 오타 때문에 8번의 불필요한 제출, 그리고 B에서 코딩 미스 때문에 2번의 불필요한 제출을 했다는 점도 너무나 아쉽다. 하지만, 이런 부분은 꾸준히 대회를 치면 잡힐거라 보..

이 라운드의 B번 문제가 올해 IOI에 제한만 높여서 나왔다고 해서 Div 1에 virtual participate 해봤습니다. B와 C를 해결했고, A는 풀지 못했으며, F는 트리 DP 같아 보였지만, 식을 세우지 못했습니다. https://codeforces.com/contest/995 Div 1B/Div 2D Suit and Tie 앞에 있는 수 부터 차례로 그리디하게 매칭해주면 됩니다. 시간 복잡도는 $O(N^2)$이 됩니다. 이 방법의 정당성은 쉽게 증명할 수 있는데, 불필요한 swap 연산이 포함되어 있지 않음을 보이면 됩니다. 적당한 자료구조를 사용하면 $O(N \log N)$으로 시간 복잡도를 낮출 수 있습니다. 아래는 제 C++ 구현입니다. #include using namespace s..

Div. 1의 문제 2개를 풀어보았습니다. 링크: http://codeforces.com/contest/1198 [Div 1C/Div 2E] Matching vs. Independent Set 정점이 $3n$개인 그래프가 주어질 때 크기 $n$ 이상인 매칭 또는 크기 $n$ 이상인 독립집합 중 하나를 찾는 문제입니다. 둘 중에 하나를 찾으라는 문제는 처음 봐서, 일단 어느 한 쪽을 먼저 찾아보기로 생각하고 접근했습니다. 대충 말해서 일반적으로 "큰" 매칭을 찾는 것은 "쉬운($\mathcal{P}$)" 문제이지만, "큰" 독립집합을 찾는 것은 "어려운($\mathcal{NP}$-hard)" 문제입니다. 그래서 큰 매칭을 찾아보기로 생각했습니다. Maximum matching을 찾는 것은 어려우니, max..

개관 어떤 배열이 주어졌을 때, 그에 대한 Cartesian Tree는 다음을 만족하는 이진 트리이다. max(min)-heap의 조건을 만족한다 어떤 노드의 값은 자식 노드의 값 보다 크다(작다) 트리를 in-order traversal 하면서 각 노드의 값을 출력했을 때 출력되는 값의 순서가 원래 배열에서 값의 순서와 같다. 구현하기 일단 이 트리의 활용성을 설명하기에 앞서, 먼저 구현 방법을 소개하도록 하겠습니다. 편의상 max-heap의 조건을 만족하게 구현한다고 합시다. 이 트리를 구현할 때는 왼쪽부터 오른쪽으로 차례로 노드를 보면서 구현해나갑니다. 각 인덱스에 대해 부모와 왼쪽 자식, 오른쪽 자식 세 가지를 관리하며 구현합니다. 초기에는 맨 첫 원소를 트리의 루트로 놓습니다. 다음의 과정을 반..

서론 UCPC 2019를 원래 bayminimum과 breakun님과 나가기로 했으나, 박사과정은 참가가 안되는 것을 알게되어 고등학교 동기들인 bayminimum과 uncertainty(3-24)와 나가기로 했습니다. 당일 새벽에 처음이자 마지막 팀 연습을 하고 온라인 예선을 참가하였는데, 결국 4솔브를 했고, 본선에 가진 못할 것 같습니다. 아쉽긴 하지만, UCPC를 계기로 손 놓았던 PS를 다시 시작하게 될 것 같아서 다행이라 생각하고 있습니다. TMI) 팀 이름은 경의중앙선으로 환승 가능이었고, 이는 bayminimum이란 친구가 집에서 서울대학교를 갈 때 배차간격이 매우 긴 경의중앙선을 탐에서 비롯하여 지은 팀명입니다. 그리고 새벽에 한 팀연습과 불면증이 더해져 2시간 자고 대회 10여분 전에 ..