선형대수학 (2) 썸네일형 리스트형 [Python] 32233번 토러스 게임 조작하기 https://www.acmicpc.net/problem/32233 24/09/12 오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다. 맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다. 문제 접근 방식: 이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다. 1. 오일러 지표에 대한 지식 2. 스프라그-그런디 정리에 대한 지식 3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식. 먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.. [Python] 32230번 현대모비스 첨단 운전자 보조 시스템 https://www.acmicpc.net/problem/32230 24/09/10 내가 출제한 문제고, 에디토리얼이 나오려면 좀 걸릴 것 같아서 미리 내 문제만 먼저 해설을 작성해보고자 한다. 문제 접근 방식: 문제의 요구 사항은 안전 영역의 최솟값을 구하는 것이다. 서브태스크별로 할 수 있는 풀이를 적고자 한다. 서브태스크 1문제를 잘 읽고 $N \geq 3$일때 볼록 다각형이 만들어지고, 그렇지 않은 경우 볼록 다각형이 만들어지지 않음을 파악한다. 따라서, $0$을 출력하면 받을 수 있다. 서브태스크 2 문제의 핵심 부분이다. 문제에서 유의 깊게 관찰할 수 있는 부분들은 $10^{-9}$과 같은 빡빡한 오차, $1$초와 같은 수상한 제한, 수상하게 큰 좌표 제한 등이 존재한다. 가장 나이브하게.. 이전 1 다음