분류 전체보기 (33) 썸네일형 리스트형 IOI 2024 Message 아직 정해를 읽지 않았지만 정황상 본인의 풀이가 정해와 다르다는 확실한 증거가 있기 때문에, 본인의 풀이를 서술해본다. 해당 풀이는 본인의 두뇌가 발상하는 과정의 순서대로 작성되었다. 일단, 1024비트 이내의 문자열이지만, 문자열의 길이가 다를 수도 있음을 고려하면 실질적으로 보내야 하는 정보량은 1025비트이다. 편의상, Cleopatra 를 캬루라고 하고, Aisha를 에나, Basma를 미즈키라고 하겠다. Observation 1. 정확히 4번 메세지를 보내서 미즈키가 어떤 안전한 위치 하나를 알도록 만들 수 있다.이를 하는 방법은, 맨 처음에 16개의 안전한 위치중 8개는 0, 나머지 8개는 1을 표기해서 보내는 것이다.캬루가 나머지 15개를 어떻게 칠하더라도, 절반 미만으로 등장하는 색깔이 존.. Asia Pacific Championship 2025 후기 생각해보니까 많은 팀들이 대회를 치고나면 그 회고록을 올리는데에 비해서 이번 APAC의 회고록을 (적어도 내가 알기로) 우리 팀원중 아무도 작성하지 않았다는 점을 깨닫고, 기억이 풍화되기 전에 미리(미리라고 하기에는 사실 한달정도가 지나긴 했지만) 후기를 작성하고자 한다. 안타깝게도 기억이 상당수 풍화되었기 때문에, 일부 서술들이 두서없고 상당수의 모순을 포함하고 있을 수 있음에 주의하라. 0. IAEPC? 참가 불가알 사람들은 알겠지만, 어떤 딥1+2 코포에서 37등을 기록했던것 같은데, 그게 사실은 어떤 대회의 예선대회격인 것이었어서 갈 수 있는 자격을 얻었었다. 만약 실제로 갔었다면 tourist, jiangly, Um_nik등을 비롯한 수많은 lgm들을 볼 수 있는 좋은 기회였겠지만, 불행히도 그.. 1.5월 PS일지(feat. [궁극의 웰노운 알고리즘] 13. Gröbner basis and Buchberger algorithm) 조금 뒤늦은 감이 있지만, 1월과 2월초 사이에 지금까지 했던 PS적인 무언가들에 대해서 포스팅을 쓰고자 한다. 우선, 나름대로 어찌하여 이렇게 포스팅이 늦었는가에 대한 변론을 하자면, 최근에 봉사시간을 채울 필요가 있어서 일주일동안 봉사시간을 30시간 채울 필요가 있었고, 또한 방학중 진행되는 스터디에 참여 및 준비를 하느라 PS할 시간이 부족했다... 그래도 나름대로 PS를 아예 안한 것은 아니므로 시작하겠다. 1. Gröbner basis and Buchberger algorithm다음의 글을 참조하라: https://infossm.github.io/blog/2025/01/31/Buchbergers-algorithm/ 2. PS일지2.1. https://www.acmicpc.net/problem/3.. 1월 PS일지(1) (feat. [궁극의 웰노운 알고리즘] 12. Lagrange interpolation) 저번에 예고하였던 대로, 궁극의 웰노운 알고리즘도 작성할 겸 PS일지도 쓸 겸 글을 작성하게 되었다. 총 2개의 ARC와, 총 1개의 다3 수학문제를 풀었으며, 한 개의 요코하마 셋을 돌았다(이전에 내걸었던 공약에 비해 한 것이 많지 않아보인다면, 사실이다. 다만 지난주동안 바빴어서 어쩔 수 없었다.). 또한, 앞으로는 그냥 PS일지에다가 궁극의 웰노운 알고리즘을 작성할 예정이다. 암튼, 일단은 궁극의 웰노운 알고리즘부터 설명을 하겠다. 1. Lagrange Interpolation사실, 이 주제는 별로 언노운은 아니고 아마 많은 사람들이 알고 있는 테크닉일 것이라고 생각한다. 그냥 핵심부터 말하자면, d차 다항식은 점 d+1개가 주어질 시 유일하게 결정된다는 것이다. 해당 글에서는 Lagrange In.. [ROAD TO ULTIMATE MATHCHUNG] 2. Bus Stop https://www.acmicpc.net/problem/18570원래는 오늘 풀 문제가 있었는데 하루종일 자다보니까 시간이 많이 지나버려서 그냥 눈에띄는거 하나 잡아서 빠르게 쌀먹했다. 일단, 당연히 아무 버스가 도착하는 시간은 모든 버스를 통틀어서 최소 주기보단 작거나 같을 것이다. 이를 T라고 하자. 또한, 아무 버스가 도착하는 시간의 확률변수를 t라고 하자. P(t>=x)는, 모든 버스가 x분보다 빠르게 도착하지만 않으면 되기 때문에, ∏k=1n(ak−x)∏k=1nak=f(x)와 같이 기술할 수 있다. f(x)를 미분하고 -1을 곱하면, 확률밀도함수 p(x)를 얻는다. 기댓값은 xp(x)를 x:0~T까지 적분한 값이라는 사실을 알 수.. [ROAD TO ULTIMATE MATHCHUNG] 3/2. Atcoder Regular Contest 104 https://atcoder.jp/contests/arc104/tasks Tasks - AtCoder Regular Contest 104AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp104번 콘테스트부터 하는 이유는, 최근의 앳코더 형식과 비슷하게 출제되기 시작한 시점이 104번 콘테스트부터이기 때문이다. A. 자명. B. (i,j)가 실제로 가능한지 판별하는 방향으로 한다. (i,j) 구간에서 A개수가 T개수와 같고, C개수가 G개수와 같다면 가능하다. 따라서 모든 i에 대해서, j를 증가시키며 문제를 풀 수 있다. C... [ROAD TO ULTIMATE MATHCHUNG] 1. Graph Counting https://www.acmicpc.net/problem/18453문제를 아주 간단히 요약하자면, 그래프 자체로는 완전매칭이 없는데, 간선을 아무거나 하나 추가하면 완전매칭이 생기는 non-isomorphic한 정점 2n개의 그래프의 개수를 세는 것이다(n≤500000). 한가지 중요한 정리를 사용한다:https://en.wikipedia.org/wiki/Tutte%E2%80%93Berge_formula Tutte–Berge formula - WikipediaFrom Wikipedia, the free encyclopedia Characterization of the size of a maximum matching in a graph In this graph, removing one.. [궁극의 웰노운 알고리즘] 11. Partition number, Euler's Pentagonal Theorem 저번 글에서 예고한 대로, 궁극의 웰노운 알고리즘을 작성한다. 사실 이 주제에 대해서는 굳이 글을 쓸 생각은 없었다만, 그래도 나름 알고있으면 아주 못써먹을 정도는 아닌 알고리즘이라고 생각되어 포스팅하는 것이 낫다는 결론에 이르렀으며, 무엇보다 문제를 풀다가 한 번 더 마주치게 된 알고리즘이라서 포스팅하게 되었다. 1. Introduction다음과 같은 문제를 생각하자: 정수 n이 주어진다. 당신은 P(n)(즉, n번째 분할수)을 출력해야 한다. 분할수에 대한 기초적인 이론은 중등 KMO 수준에서도 자주 다루기 때문에 이 문제가 그리 어렵지 않게 풀릴 것이라고 예상할 수도 있지만, 생각보다 이 문제는 빠른 시간 내에 해결하는 것이 쉽지 않다. 아, 참고로 분할수라는 것이 무엇인.. 이전 1 2 3 4 5 다음 목록 더보기
