600문제는 아마 영원히 못 풀지 않을까?

'PS > 수학 계열 PS' 카테고리의 다른 글

Project Euler 550+  (0) 2021.04.09
8월의 PS 일지 - Part 5  (0) 2020.08.12
8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16

BOJ 19245 XOR

BOJ 19078 New Divide

BOJ 19273 XorTree

BOJ 19458 Expected LCP

BOJ 18956 Little Q and Big Integers

BOJ 19570 삼각 분할

BOJ 19424 Power of Power Partition Function


'PS > 수학 계열 PS' 카테고리의 다른 글

Project Euler 550+  (0) 2021.04.09
8월의 PS 일지 - Part 5  (0) 2020.08.12
8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16

추가적으로 더 해결한 수학 문제들과, 최근에 친 AGC 문제들을 다룬다.


BOJ 15983 순간이동 발판

BOJ 19302 XOR Transformation

BOJ 19390 Coprime Queries

BOJ 19138 GCD vs LCM

BOJ 19495 Square Function

AGC 047

출처는 잘 모르는 문제. 

입력으로는 $a, N$이 주어지며, 이때 $1 \le x \le y \le N$, $\text{gcd}(x, y)=1$, $x|y^2+a$, $y|x^2+a$를 만족하는 $(x, y)$의 개수를 구해야 한다. 

$1 \le a \le 10^5$, $1 \le N \le 10^{18}$. 테케는 총 $10^6$개가 있으며, 전부 5초 내에 해결해야 한다. 메모리 제한은 256MB.


'PS > 수학 계열 PS' 카테고리의 다른 글

Project Euler 550+  (0) 2021.04.09
8월의 PS 일지 - Part 5  (0) 2020.08.12
8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16

BOJ 19549 레이저 연구소

BOJ 18975 Jaw-Dropping Set

BOJ 19069 Rock-Paper-Scissors

BOJ 19003 Rikka with Equation

BOJ 19000 Rikka with Proper Fractions

BOJ 18764 LCM Sum


'PS > 수학 계열 PS' 카테고리의 다른 글

8월의 PS 일지 - Part 5  (0) 2020.08.12
8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02

Hackenbush에 대한 간단한 튜토리얼을 쓰려고 하는데, 내가 이걸 잘 아는 거는 아니라서 (...) 증명 및 깊이 있는 이론들은 (ordinal 등장 등) 대부분 생략하고 알고리즘 문제 풀이에 써먹을 수 있는 부분들만 간략히 추려서 쓰려고 한다. 자세한 증명은 구글에 검색하면 자료가 매우 많으니 찾아보는 것을 추천한다 :)

 

Hackenbush 게임은 두 명이서 하는 게임으로, 여러 가지 버전들이 존재하지만 근본적인 목표는 똑같다.



위 그림과 같이, 일종의 그래프가 지면에 연결되어 있는 상태에서 게임이 시작된다. 

각 플레이어는 순서대로 간선 하나를 제거하는데, 이때 더 이상 지면에 연결되지 않게 되는 간선들은 모두 삭제된다.

일반적인 룰에서는 (normal play convention) 간선을 제거하지 못하게 되는 플레이어가 패배한다.

간선이 무한히 많은 경우도 존재하지만, 여기에서는 유한한 개수의 간선이 존재한다고 가정한다.

그러면 게임이 확실하게 Sprague-Grundy 방식으로 분석이 가능해진다. 이를 위해서 다음 Principle을 활용한다.


Colon Principle: 그래프 $G, H, K$가 있다. $H, K$의 Grundy 값이 같다면, $G$의 정점 $x$에 $H$를 붙인 그래프와 $x$에 $K$를 붙인 그래프의 Grundy 값이 동일하다. 그러므로, 한 점에서 '가지치기'가 되는 그래프가 있다면, 각 가지들의 Grundy 값의 XOR에 해당하는 길이의 일직선을 붙이는 것으로 가지들을 대체할 수 있다. 이를 통해서 트리 그래프에 대한 분석을 끝낼 수 있다. DFS를 돌면서 서브트리의 Grundy 값을 순서대로 계산하면 된다.


Fusion Principle: 두 정점이 한 사이클 위에 놓인다면 (지면을 하나의 노드로 본다) 두 점을 하나로 합쳐도 Grundy 값이 변하지 않는다. 

이때 두 점을 잇는 간선들은 self-loop가 된다. 이 성질을 이용하면, 임의의 그래프에 대한 Grundy 값을 구할 수 있다.

실제로 이를 활용하는 문제는 본 적이 없지만, 아무튼 이를 이용하면 기본 Hackenbush에 대한 분석은 끝이다.


연습문제: Project Euler 400 Fibonacci Tree Game, BOJ 13893 Dictionary Game

두 문제 다 Hackenbush에 대한 이해와 적당한 구현을 (DP/Trie 등) 통해서 해결할 수 있다. Fusion Principle은 필요 없다.


Blue-Red Hackenbush는 조금 색다르다. 이제는 각 간선마다 누가 자를 수 있는지가 둘 중 한 명으로 정해져 있다.

각 플레이어를 Blue/Red라고 하고, Blue 간선은 Blue만, Red 간선은 Red만 자를 수 있도록 한다.

이때는 각 연결 컴포넌트 $G$에 대하여, 그 컴포넌트의 값 $v(G)$를 다음과 같이 재귀적으로 정할 수 있다.

아무것도 없는 그래프의 경우 값은 자명하게 $0$이다. $G$가 nonempty라고 가정하자.

$b$를 Blue가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최댓값이라 하자. 불가능한 경우 $-\infty$.

$r$을 Red가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최솟값이라 하자. 불가능한 경우 $\infty$.

만약 $b < n < r$인 정수 $n$이 존재한다면, $v(G)$는 해당하는 정수 $n$ 중 $0$에 가장 가까운 것이다. 

그렇지 않다면, $v(G)$는 $b < x < r$을 만족하는 유리수 $x$ 중 분모가 $2$의 거듭제곱인 것 중에서 분모가 최소인 것이다. 


또한, 독립적인 그래프 $G, H$에 대하여 $v(G+H) = v(G) + v(H)$가 성립한다.

만약 $v(G) > 0$이라면 Blue가 승리, $v(G) < 0$이라면 Red가 승리, $v(G)= 0$이라면 후공 승리가 된다.


이 게임에 대한 직관적인 이해를 원한다면 stonejjun의 블로그를 찾아보는 것을 추천한다.


이걸 모두 짬뽕한 Blue-Red-Green Hackenbush도 있는데, 이건 진짜 무서워 보인다 ㅋㅋ


연습문제: BOJ 13409 Black and White Boxes, BOJ 18945 조직된 ㄱ폭탄 게임

13409는 Hackenbush 값을 계산한 다음 Meet In The Middle을 하면 간단하게 해결할 수 있다.

18945는 몇 가지 관찰을 한 다음, 문제를 Blue-Red Hackenbush로 변형하여 해결할 수 있다.


이 글의 진짜 목적 중 하나가 18945의 풀이를 적는 것이니, 여기에 소개한다.

각 게임을 독립적인 Blue-Red Hackenbush 게임으로 보고, 그에 대응하는 값을 계산하자. 

그러면 남은 쿼리들은 전부 단순한 point update range query 문제가 되므로, 펜윅/세그먼트 트리를 이용하여 계산할 수 있다. 

그러니 문제 난이도의 99%는 각 게임을 Blue-Red Hackenbush 게임으로 변환하는 것에서 나온다. 


일반성을 잃지 않고 A 폭탄이 하나 존재한다고 가정하자. 그러면 B 폭탄을 3가지 종류로 나눌 수 있다.

종류 1: A 폭탄이 터지면 강제로 제거되는 B 폭탄들

종류 2: 터뜨리면 A 폭탄이 터지게 되는 B 폭탄들

종류 3: A 폭탄과 서로 interact 할 수 없는 (즉, 하나가 터져도 다른 하나가 터지지 않음) B 폭탄들


이 게임판에서 A가 할 수 있는 행동은 단순히 A 폭탄 하나를 터뜨리는 것 뿐이다. 

B가 할 수 있는 행동은 다양한데, 실제로 고려해야 하는 것은 몇 가지 없음을 알 수 있다.

우선 종류 3의 폭탄과 같은 경우에는 애초에 A 폭탄이 터지던 말던 상관이 없기 때문에, 최대한 마지막에 터뜨리는 것이 좋다. 

물론, 자신이 터뜨린 폭탄에 의해 자신의 다른 B 폭탄이 쓸데없이 터지지 않도록 순서를 잘 정해서 터뜨려야 한다.

종류 2의 폭탄은 터뜨린다면 강제적으로 종류 1의 폭탄 중 남아있는 것은 무조건 터지게되며, 경우에 따라서 종류 3의 폭탄 역시 터질 수 있다. 

그러니 A 폭탄을 제거할 목적으로 종류 2의 폭탄을 터뜨린다면 종류 3의 폭탄을 최소한으로 터뜨리도록 하는 폭탄을 하나 찾아서 그걸 터뜨려야 한다.  

종류 1의 폭탄은 터뜨린다면, 다른 종류 1의 폭탄을 터뜨리지 않도록 행/열 순서를 잘 잡아서 순서대로 터뜨려야 한다.


이를 종합하면, 다음과 같은 Blue-Red Hackenbush 그림을 그릴 수 있다. A가 Red, B가 Blue라고 하자.



그래프가 특수한 형태를 가진다. 그러니, 이와 같은 경우에서 Hackenbush 값은 아예 closed form 식을 통해서도 구할 수 있다.

나는 DP를 이용하여 위에서 설명한 규칙을 직접 적용하는 방식으로 구현했다. 분수를 다루기 귀찮으니, 적당히 큰 2의 거듭제곱을 곱해줘서 다루면 편하다. 

'PS > 수학 계열 PS' 카테고리의 다른 글

8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02
4월의 PS 일지 - Part 4  (1) 2020.04.25
  1. Sait2000 2020.05.18 00:58

    팬이에요
    저는 그림 안 그리고 그냥 surreal 왼쪽 오른쪽만 열심히 나눴네요 신기하네요...
    종류 123 나누고 surreal 왼쪽 오른쪽 열심히 나눴는데 2 터트려도 3이 안 터지는 거를 빼먹어서 등등 꽤 고생했어요

바쁘기보다는 게을러서 PS를 안했다. 또 수학 PS 연습을 팠는데, 슬슬 머리가 터질 것 같고 진짜 PS가 하고 싶어졌다.

2주간 진행한 연습에서 6/12문제를 해결하였다. 그 중 단순한 사전지식 문제도 꽤 포함되어 있다.

아래에 소개한 내용 외에도 5월에는 Project Euler 715를 풀었는데, 5등을 기록했고 만족하고 있다. 

Thread에도 꽤 유의미한 내용을 두 개 제공해서 kudos도 많이 받고 기쁘다. 이 기회에 Eulerian 랭킹 상위권을 시도하려고 한다.

GCJ Round 2도 쳤고 작년보다는 등수가 많이 떨어졌고 뇌절도 많이했지만 아무튼 티셔츠는 받아서 다행이다.

감이 엄청 떨어진 것 같으니 시간나면 플레티넘 문제부터 다시 차근차근 푸는 연습을 해야겠다.

또한, 지금 진행되고 있는 대회인 Semi-Game Cup의 검수를 맡아서 몇 문제 풀었다. :)



BOJ 18465 Horrible Cycles (K, Ruby V)

BOJ 18630 Lati@s (J, Ruby IV)

BOJ 18461 Disjoint LIS (I, Ruby IV)

BOJ 10057 Pachinko (L, Ruby V)

BOJ 18622 Dedenne (H, Ruby IV)

BOJ 17160 Traffic Blights (G, Ruby IV)


'PS > 수학 계열 PS' 카테고리의 다른 글

8월의 PS 일지 - Part 1  (0) 2020.08.04
Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02
4월의 PS 일지 - Part 4  (1) 2020.04.25
Project Euler 500문제 및 문제 추천  (0) 2020.04.12

연습을 계속하고 있다. 21/26 문제를 해결하는 것으로 일단 종료. 4월에 시작한 연습이니까 4월 카테고리에 넣는다.

남은 문제들은 다 너무 어려워서 못 풀겠다. 일단 수학 PS는 질리도록 했으니 다른 것부터 하는 게 좋을 듯.



4월 30일


BOJ 5627 박테리아 (T, Diamond III)

BOJ 12735 Boat (R, Diamond III)

BOJ 18480 Four Elements (H, Ruby V)


5월 1일


BOJ 18297 Pixels (O, Diamond III) 


5월 2일


BOJ 14639 Replicate Replicate Rfplicbte (N, Diamond II)

BOJ 18527 All Kill (I, Ruby IV)

BOJ 18574 Fractional XOR Maximization (E, Ruby V)


5월 4일


BOJ 18791 N의 배수 (2) (Y, Diamond III)

BOJ 18792 N의 배수 (3) (Z, Diamond I)


'PS > 수학 계열 PS' 카테고리의 다른 글

Brief Introduction to Hackenbush Games  (1) 2020.05.17
5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02
4월의 PS 일지 - Part 4  (1) 2020.04.25
Project Euler 500문제 및 문제 추천  (0) 2020.04.12
2월의 PS 정리 - Part 3  (3) 2020.02.29

수학 문제를 더 풀고 싶어서 (집 나간 수학 근본 찾고 싶어서) 26문제 연습셋을 만들고 풀고 있다. 

글을 쓰기 시작한 4월 25일 오후 3시 시점에서는 12문제를 해결했다. 우선 이 문제들부터 풀이를 작성한다.

26일, 27일에는 갑자기 일이 생겨서 + 게을러져서 문제를 해결하지 못했다. 대신 풀이는 몇 개 생각한듯.



4월 21일


BOJ 18743 Bin (K, Ruby V)


4월 22일


BOJ 17118 갓 소수 (W, Diamond V)

BOJ 17993 Elven Efficiency (U, Diamond III)


4월 23


BOJ 18556 Count The Sequences (D, Ruby V)

BOJ 18718 Bags of Candies (P, Diamond II)


4월 24일


BOJ 18745 Div (L, Diamond I)

BOJ 18607 Domino Covering (A, Ruby II)

BOJ 11609 Particle (X, Diamond V)

BOJ 18746 Exp (M, Diamond I)

BOJ 8134 Crystals (Q, Diamond III)


4월 25일


BOJ 1140 요금 (S, Diamond III)

BOJ 18347 완벽한 순례 (V, Diamond IV)


'PS > 수학 계열 PS' 카테고리의 다른 글

5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02
4월의 PS 일지 - Part 4  (1) 2020.04.25
Project Euler 500문제 및 문제 추천  (0) 2020.04.12
2월의 PS 정리 - Part 3  (3) 2020.02.29
JAG Summer Camp 2018 Day 2  (0) 2020.02.19
  1. 2021.08.24 21:36

    비밀댓글입니다