정상적인 풀이 (4) 썸네일형 리스트형 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 다음
