전체 글 10

Solved.ac Grand Arena 후기 (?)

고수가 많다 :fearful: 그래도 한 문제 빼고 다 풀어서 행복했다 :thumbsup: 전체적으로 codeforce 느낌이 나는 셋이었다. 대략적인 풀이(스포) A - 구현하면 된다. B - 구현하면 된다. C - 나는 그리디로 풀었다. 앞에서부터 현재 합을 구하면서 현재 수가 음수면 현재 합이 양수고 더해서 음수가 되는 상황이 아니라면 이전 것과 병합한다 현재 수가 양수면 현재 합이 양수거나, 현재 합에 더해서 음수가 되는 상황일 때 이전 것과 분리한다. 를 반복하면 풀 수 있다. D - 못풀었다. 뭔가 세그같은 냄새가 난다. E - 어떤 수 a가 있을 때, a mod K + b mod K 가 0일 경우 a와 b는 같은 조합에 존재할 수 없다. 이 사실을 알면 간단한 조합론 문제로 풀 수 있다. F..

PS 2023.08.06

Dhyang's method (2.5) 이게 이미 있었네

안녕히 계세요 여러분! 전 이 세상의 모든 굴레와 속박을 벗어 던지고 제 행복을 찾아 떠납니다! 저는 지난 시간에 다음 시간을 예고한 다음, 잠적했습니다. 근데 오늘 찾아보니까 굳이 D-index(더러운 index)를 사용하지 않더라도 루프가 있는 게임의 winning strategy (if there is any) 를 찾는 방법이 존재하더라고요? 이게 이미 있었네 혹시 궁금하신 분은 https://www.sciencedirect.com/science/article/pii/0097316586900580 를 보시거나, 대충 google scholar 같은 웹사이트에 generalized Sprague-Grundy theorem을 찾아보시면 나옵니다. 근데 많이 더럽긴 해요 대충 설명을 하자면, 1. Gen..

PS 2023.08.02

Dhyang's method (2) 그래서 이게 왜 되는거죠

짜잔, 사실 속으신 거에요! 우선, D-index를 계산하는 데에는 사실 O(M^N) 이 걸리지 않습니다. D-index의 set size가 1인 경우만 예외로 두면, 적절히 숫자를 선택해서 어떤 range에 구멍이 뚫린 모양의 D-index를 얻을 수 있습니다. 따라서, D-index를 O(MN log N) 과 유사한 속도로 구할 수 있을 것입니다. (자세한 증명은 되어있지 않습니다!) 싸우실래요 D-index를 게임 내에서 구하는 방법을 정의했으니, D-index의 xorsum 연산 (sprague grundy theorem을 적용시키기 위해서) 또한 생각해 봅시다. 마찬가지로, 모든 Game-state의 D-index의 모든 combination을 구해서, 이 combination들의 xor 값들을..

PS 2023.06.13

Dhyang's method (1) 그런디 말입니다...

그런디 말입니다... 좀 더 알아봐야겠습니다. 이 글에서는 제가 발견한, Sprague-Grundy theorem을 조금 더 다양한 상황에서 exploit할 수 있게 하는 방법을 다룹니다. Sprague-Grundy theorem Sprague-Grundy theorem은 impartial game에서 효과적으로 두 개의 게임을 하나의 게임으로 취급할 수 있게 합니다. Impartial game의 조건은 다음과 같습니다. 각각의 플레이어는 게임이 끝날 때까지 턴을 가져야 하고, 턴을 가지지 못하는 상태를 패배한 상태로 합니다. (misere는 일반 nim으로 바꿀 수 있으므로 이 글에서는 다루지 않겠습니다.) 게임은 유한해야 합니다. 이 때문에 루프가 있는 게임이거나 비길 수 있는 게임은 Sprague-..

PS 2023.06.12

아니메컵 후기

1쿨과 2쿨에 7문제를 출제했습니다. 결론 제가 출제한 문제는 1쿨의 DEG, 2쿨의 CEFM이였습니다. 가 아이디어를 낸 7문제의 평균 정답률은 20.04%였습니다. 아무래도 제 문제들이 꽤나 앞쪽에 배치되어 있었음에도 불구하고, 무언가 살짝씩 이상한 문제들이라서 본의치 않은 3+솔 진입장벽이 되버린 느낌입니다. 그럼에도 불구하고, 잘 푸시는 분들은 쉽게 푸시더라고요 저는 세팅을 하지 않았지만, 많은 분들이 도와주셔서 정상적으로 (?) 문제가 출제되었습니다. 발단 sait2000님이 아니메컵이 열릴 수도 있다는 말을 하셨습니다. 구경하려는 마음가짐으로 대회 디스코드 서버에 들어갔습니다. 뭔가 아이디어가 많이 생각나서 적었습니다. 아이디어가 너무 많아져서, 1쿨/2쿨로 대회가 쪼개졌습니다. 그리고 제 원..

PS/PS 외적인 것 2023.02.13

BOJ 27077 16강과 쿼리

???: 16강 가면 문제를 하나 출제하겠습니다. 공약을 지켜야만 한다. 문제 이름에 '쿼리' 가 들어가 있어 무서워 보이는 문제이지만, 실제로 주어지는 데이터의 개수가 그리 많지 않아 naive한 솔루션이 시간 안에 통과됨은 쉽게 알 수 있다. 그러하기 때문에 이 문제의 주된 난이도는 구현에서 오는데, 시간 복잡도가 굉장히 널널하므로 각 상황마다 끝난 후 상황을 구한 후, sorting 해 한국이 몇등에 가는지, 한국과 동률인 팀은 있는지를 적절히 체크하는 것이 가장 쉬운 구현 방법이다. sorting의 parameter를 설정하는 것이 조금 까다로울 수 있는데, 이는 sorting을 직접 구현하거나, compare함수를 구현하는 것으로 풀 수 있다. 전체적으로 쉬운 문제를 만들고자 한 만큼, 정답 코..

PS 2023.01.04

BOJ 25517 머리 아픈 암산은 이제 그만!

처음으로 출제한 문제다. 검수하시는 분들이 이상한 부분들을 많이 찾아주셔서 그래도 정상적인? 퀄리티의 문제가 만들어 진 것 같다. 답안 스포일러: 더보기 문제에서 주어진 N은 10**9로, O(N) 이상의 시간복잡도를 가진 경우 풀 수 없다. modular 가 정해져있다는 점 을 이용해 특정 구간의 숫자들의 팩토리얼을 미리 전처리 해 놓고, N! 에서 입력받는 숫자중 겹치지 않는 숫자들을 하나하나 modular inverse 를 구하여 나누어 주면 된다. datas = [1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970..

PS 2022.08.24

2022 KOI 고등부 본선 후기

총 24 / 100 / 100 / 0 으로 224점, 가채점 결과로 34등 상위 18% 동상이 나왔다. 시험 양상 시작하자마자 문제들을 모두 읽었다. 1번은 트리여서 우선 넘겨놨고, 4번은 손도 못댈거같아서 치워놨다. 2번과 3번 둘다 무언가 기시감이 드는 문제였지만, 구현이 3번 먼저 생각나서 3번 먼저 코드를 짜기 시작했다. 3번은 무난하게 예외처리하고 디버깅하니 100점을 받을 수 있었다. 3번을 푼 이후 1번으로 넘어왔는데, dfs에서 벗어나지 못한 나머지 시간을 많이 날렸다. 진전이 없어 보여서 2번을 봤다. 내가 생각한 2번 해답 구현이 생각보다 어려운 문제여서 시간을 꽤 쓰고 100점을 받았다. 1번으로 돌아왔는데 dfs에서 벗어나지 못하고 어떻게든 최적화하려다가 실패하고 24점을 받게 되었..

PS 2022.07.24