너무 많이 쉬었더니 PS실력이 집을 나가버렸다.ko_osaga님의 추천으로 ARC를 최근 것부터 밀어보기로 했다. EF는 어려우니까 CD부터. 물론 D마저도 몇 개 못 풀었다... 은퇴를 고려해야 하나. C는 대부분 간단한 관찰로 밀어버릴 수 있는 문제같다. 코드도 400B 안쪽으로 나오는 것 같으니 웬만큼 좋은 문제가 아니면 포스팅하지 않을 계획. 오늘 푼 문제(6 / Total 6) : ARC102C (Triangular Relationship)ARC102D (All Your Paths are Different Length)ARC101D (Median of Medians) #오늘 푼 문제는 아닌데 괜찮은 문제라서 포스팅.ARC100C (Linear Approximation)ARC098C (Attent..

아직 공부중인 자료구조 / 알고리즘들이다.세상에 똑똑한 사람이 너무 많아.. 1. DP tricks 1.1. Alien Trick (Wang Qing-Shi Binary Search) 구사과 블로그imeimi 블로그원문을 구할 수 있는 곳 (중국어) IOI 2016 AliensNAIPC 2017 Blazing new trails 1.2. dynamic CHT (without pointer) 일명 성적CHT. 본지가 언제인데 아직도 못 짜냐 ㅡㅡ 1.3 Li-Chao tree Doc2 csacademy 연습문제 1.4. Knuth Optimization with rigorous proof 2. Offline Dynamic Tricks 2.1. Offline Dynamic Connectivity 2.2. D..

어떤 행렬의 Reduced Row Echelon Form이 유일하다는 정리이다. 선형대수학 시간에 발표를 맡았다. SlideShare에 올려둔 ppt

Yandex 채점(Day 1) 현재 스코어 100 / 600. 과연 추가할 수 있을런지는 모르겠다...myungwoo님의 블로그에서 (아마) 모든 문제의 풀이를 확인할 수 있다. 아직은 보지 않은 상태. 18.09.05 P1 solved. P1. Combo 꽤 괜찮은 interactive 문제. IOI치고 너무 쉬워서 만점자가 240명 가까이 나왔다는 게 유일한 흠이다.길이 \(N\)인 미지의 문자열 \(S\)가 주어진다.\(S\)에 주어진 특징은 A, B, X, Y 4개의 문자로 이루어져 있다는 것이고, \(S\)의 첫번째 문자는 \(S\) 안에서 다시 등장하지 않는다는 것이다. 이 때 다음의 함수 press(p)를 최대 \(N+2\)번 호출하여 \(S\)를 찾아야 한다 : 길이가 \(4N\) 이하인 ..

\(\pi\)가 무리수임을 증명하는 과정이다. 주요 관찰들은 유용해 보이긴 한데 풀이 전체가 너무 비직관적이라... 완전히 마음에 들지는 않는다. 더 나은 풀이나 이 풀이에 대한 다른 해석이 있다면 제보 바랍니다. 실제로는 \(\pi^2\)이 무리수임만 보여도 충분하다. 증명은 \(\pi^2 = a/b\)라고 놓은 뒤에 \(a\)가 어떤 자연수도 될 수 없음을 보이는 방향으로 설계한다. Proposition 1. 정수 계수 다항식 \(f(x)\)를 생각하자. 임의의 자연수 \(n\)과 정수 \(k\)에 대해서 \(f^{(n)}(k)\)는 \(n!\)의 배수이다. 증명 생략. 이 때 \(f(x) = \frac{x^n(1-x)^n}{n!}\)을 생각하자. 여기서 \(f(x)\)의 특징을 몇 가지 뽑아낼 수 ..

문제 링크 내가 만든 엘리베이터 2 (더 강한 문제) This section is intentionally left blank. 이런 문제는 왜 중등부 지역본선에 나오는 걸까? 그 당시 중학생들은 뭐하는 사람이었던 거지 ㄷㄷ 1. Naive\(O(M^2 N)\) 두 엘리베이터가 이어져 있다면 cost 1의 간선을 연결해주고 BFS를 돌리면 된다.엘리베이터 \(i\), \(j\)의 연결을 판별하기 위해 1층부터 \(N\)층까지 돌면서 이 층이 두 엘리베이터가 공유하는 층인지 단순 나머지 연산으로 확인해주면 다음의 복잡도를 얻는다.안타깝게도 이 방식으로는 TLE를 피할 수 없다. 2. Clever\(O(MN)\) imeimi2000의 풀이 방식이다.그래프의 정점을 에지로 보지 않고 \(N\)개의 층으로 두자..