정상적인 풀이 (6) 썸네일형 리스트형 [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\le 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.. JOI 2022 리뷰 다행히도 의지를 잃지 않고 두번째 셋을 쳤다. 첫 셋보다는 비교적 열정적으로 돈 것 같긴 하다. 뭐 근데 완전히 풀집중한건 아니고 그냥 적당한 고민속도로 문제를 푼거라서 다음에는 "더 열정적으로" 칠 필요성을 느꼈다. 아무튼, 셋 리뷰나 하겠다. 1. intercastellar (?) 어렵지 않다. 대충 2로 나뉠 수 있을만큼 나누고 투포인터로 처리하면 된다. 쿼리가 정렬되어있지 않았다면 구현량이 조금 늘어서 귀찮았을 것 같은데 다행히도 정렬되어있어 굉장히 짧게 코드를 짤 수 있다. 얻은 점수는 100점 2. self study 전형적인 유형의 파라메트릭 서치. 처음에 a>b인 모든 것들에서 a만을 써서 최대한 해보고, 이제 남은 것들을 b만을 써서 덮어낼 수 있는지 확인하는 문제를 로그번 풀면 해결된다.. COI 2017 리뷰 아주 오랫만에 블로그를 쓰는데 음...이유는 생략한다. 방학이 시작했고, 고1 여름방학 이래로 최초로 수올준비를 하지 않는 방학이 와서 ps와 수학공부에 온 초점을 맞출 생각이기 때문에, 이틀에 한번씩 셋을 돌고 업솔빙까지 완료하는 계획을 세웠다.(물론 이번 셋은 업솔빙을 전부 하진 못했다.) 아무튼, 이번에 돈 셋은 COI 2017(크로아티아 정올)이다. 생각보다 문제가 많이 매웠다. 또한 5시간짜리 셋이긴 하나, 깨어나자마자 비몽사몽한 상태에서 셋을 돌고 중간에 학원에 가야 했던 일, 생각보다 의지박약때문에 설렁설렁 친 것 때문에 그다지 부분점수도 안 긁고 성적이 딱히 좋지는 않다. 잡담은 이쯤까지 하고, 각 문제들에 대한 솔루션과 나의 접근에 대해 서술하겠다. 1. ili 일단 n,m 제한이 살벌해.. 백준 27092 - 생물 연구 문제를 요약하자면, 크기가 2 이상이면서 동일한 높이이며, 최소 공통 조상이 전부 동일한 정점의 집합의 개수를 세는 것이다. 정해를 읽어봤는데 생각과는 달라서 작성하게 되었다. 우선, 제곱 풀이를 생각해볼 수 있다. tree dp를 돌리면서, 어떤 서브트리의 루트를 최소 공통 조상으로 하는 집합의 개수를 세는 것이다. 만약 각 서브트리가 특정한 깊이를 가진 정점의 개수를 들고 있다면, 한 서브트리에서 문제의 답에 더해주어야 할 것은 각 높이에 대해, 각 서브트리가 가진 정점의 개수를 전부 곱한 값(그 높이의 정점이 존재하는 서브트리가 2개 이상인 경우에 한하여)을 전부 더해주면 된다는 사실을 직관적으로 알 수 있다. 다음과 같은 경우에, 1번 정점을 기준으로 카운팅해보자. 2번 정점을 루트로 하는 서브트.. 백준 7936 - N의 존재 7936번: N의 존재 (acmicpc.net) 문제 자체가 워낙 간결해서 굳이 문제를 요약할 필요는 없을 것 같다. 우선, 정수론적인 사전지식이 몇가지 필요하다. 원시근과 이산로그에 대해 알고 있다면 해당 문제의 풀이를 이해하는데에 지장이 없을 것이다. 만약 p에 대한 원시근을 하나 찾는다면 문제가 해결되었다고도 할 수 있다. n을 p씩 올리는 행동을 n^m 항에는 어떤 영행도 미치지 않지만, n^n항에서는 지수가 정확히 1 늘어난 효과를 보여준다. 따라서 원시근을 일단 찾고 나면, n^n === a-n^m(mod p)인 문제를 해결하게 된다. 이때 n을 p씩 늘린다고 하였기 때문에, 그 원시근을 거듭해서 곱해주는 효과가 나타난다. 이 방법을 통해 특정한 값에 도달할 수 있는가는 이산로그 문제를 해결함.. 이전 1 다음
