스프라그-그런디 정리 (20) 썸네일형 리스트형 [Python] 29154번 작곡가 A의 시창 평가 https://www.acmicpc.net/problem/29154 24/05/16 이전에 해결했었던 스그 문제인데, 꾸역꾸역 kmp랑 엮어서 만들었다는 느낌을 너무 강하게 받은 문제이다. 문제 접근 방식: 일단 선/후공 승패 여부 판단하고, 색칠된 부분이 여러 개의 모습으로 분리되며, 색칠된 부분을 그냥 님게임으로 간주할 수 있다는 사실은 스프라그 그런디 정리를 많이 풀어본 사람이라면 쉽게 파악할 수 있을 것이다. 문제는 그러면 색칠된 부분을 어떻게 빠르게 구할건데?가 핵심이 된다. 보면 멜로디 $L$과 멜로디 $L$의 접미사들을 "모두" 기존 문자열 $S$에서 찾아야 한다.(빠르게) 그러면 당연히 생각나는건? kmp다. kmp의 동작 원리를 생각하면 접두사와 접미사가 일치하는 부분을 통해 "당겨옴.. [Python] 32233번 토러스 게임 조작하기 https://www.acmicpc.net/problem/32233 24/09/12 오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다. 맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다. 문제 접근 방식: 이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다. 1. 오일러 지표에 대한 지식 2. 스프라그-그런디 정리에 대한 지식 3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식. 먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.. [Python] 32213번 래빗 홀 https://www.acmicpc.net/problem/32213 24/09/05 간단한 스프라그-그런디 문제이다. 관찰의 아이디어가 좋아서 작성해본다. 문제 접근 방식: 두 사람이 할 수 있는 행동은 동일하다. 둘 중 하나이다. 1번 행동은 일반적인 님 게임이다. 근데 걸리는 점은 2번 행동이다. 2번 행동이 1번 행동에 영향을 줄 수 있을까, 곰곰히 생각해보면 아니다. 얼핏 생각하면 영향을 줄 수 있을 것 같지만 2번 행동이 전체 XOR의 합에 영향을 끼치지 못하므로 1번 행동과 독립이다. 결국 2번 행동은 홀짝성에 관한 게임을 개별적으로 하는 것과 동치이다. 즉, 님 게임과 홀짝 게임을 동시에 하고 있는 것과 동치이다. 처음에는 이러한 사실 때문에 님게임 XOR값과 홀짝성 모두 만족하면 후공 .. [Python] 12848번 막대기 게임 https://www.acmicpc.net/problem/12848 24/05/16 간단한 스프라그-그런디 정리 응용 문제로, 게임판 분할에 관한 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 막대기를 게임판 위에 더 이상 둘 수 없는 사람이 지는 게임이다. 다행히도 막대기는 가로 모양 밖에 존재하지 않아서, 각 행 별로 게임이 분리된다는 사실은 쉽게 알 수 있다. 또한, 장애물이 있는 곳에는 막대기를 둘 수 없다는 제한 조건 때문에, 장애물이 놓여 있는 곳 별로 게임이 분리된다는 사실 또한 쉽게 알 수 있다. 따라서, 각 행 별로, 각 막대기가 놓여진 곳 별로 게임을 분리하여, 각 게임 별 그런디 수를 구하면 된다. $n > k$이고, 길이 $n$짜리 게임 판이 주어질 때, .. [Python] 8170번 Pebbles (추후 보강 예정) https://www.acmicpc.net/problem/8170 24/05/19 스프라그-그런디 문제로, 증명하기가 꽤나 어렵고 규칙을 발견하는 것도 쉽지 않은 문제인 것 같다. 나는 이 문제를 해결하기는 했지만, 왜 그렇게 나오는지에 대한 증명은 하지 않아서, 추후에 증명을 하게 된다면 보강해서 작성할 예정이다. 문제 접근 방식: 처음에 문제를 접근한 방식은 나이브한 탑-다운 DP였다. 가지고 있는 현재 조약돌의 전체 상황을 튜플로 저장하여, 그 상황을 딕셔너리에 집어넣는 풀이였다. 당연히 시간초과를 받을 수 밖에 없었는데, 잘 생각해보면 돌 더미의 개수가 최대 $1,000$개이고, 내가 어떤 게임판의 상황에서 할 수 있는 행동 또한 정말 많기 때문에 시간초과가 날 수밖에 없다. 그래서 규칙을 찾.. [Python] 31687번 Trokut https://www.acmicpc.net/problem/31687 24/05/18 스프라그-그런디 정리 문제이다. 약간 웰노운 성이 있는 것 같아서, 정리해보면 좋을 것 같아 글을 써본다. 문제 접근 방식: 문제의 접근 방식은 이전에 내가 글로 작성했던 다각형 게임과 동일하다. 심지어, 해당되는 게임조차 같다. 근데 다각형 게임의 코드를 그대로 복붙하면 시간초과를 받는다.2022.11.01 - [알고리즘/백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane [Python] 13034번 다각형 게임 / 16187번 Game on Planehttps://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이.. [Python] 27852번 Kruskal https://www.acmicpc.net/problem/27852 24/05/17 오랜만에 스프라그-그런디 정리 문제를 해결했기에 글로 작성해본다. 님 게임의 변형 문제로, 어떻게 해야 님 게임으로 치환할 수 있을지를 고민해볼 수 있는 좋은 문제이다. 문제 접근 방식: 문제에서 제시하는 상황은 다음과 같다. 일반적인 님 게임과 비슷하게, 돌 더미들이 여러 개 주어져 있다. 대신, 한 플레이어가 $1$개부터 $K$개까지 돌을 가져갈 수 있으며, 승리 조건이 어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기게 되는 게임으로 바뀌었다. 두 플레이어가 최선의 플레이를 진행한다고 할 때, 누가 이길 지를 판별하는 것이 문제의 요구조건이다. 님 게임의 변형으로 돌 개수의 제한을 두는.. [Python] 18689번 Baklawa https://www.acmicpc.net/problem/18689 18689번: Baklawa Baklawa or baklava, is a sweet middle eastern dessert, mainly made from phyllo dough sheets, walnuts, and sugar syrup cut into small cubic pieces and served in cuboid boxes containing multiple layers. Alice and Bob love to play what they call the last Bakl www.acmicpc.net 23/08/19 전형적인 스프라그-그런디 문제로, 문제의 상황을 님게임으로 변형시키기만 하면 해결할 수 있는 매우 쉬운 문제이다.. 이전 1 2 3 다음
