1.5월 PS일지(feat. [궁극의 웰노운 알고리즘] 13. Gröbner basis and Buchberger algorithm)

조금 뒤늦은 감이 있지만, 1월과 2월초 사이에 지금까지 했던 PS적인 무언가들에 대해서 포스팅을 쓰고자 한다. 우선, 나름대로 어찌하여 이렇게 포스팅이 늦었는가에 대한 변론을 하자면, 최근에 봉사시간을 채울 필요가 있어서 일주일동안 봉사시간을 30시간 채울 필요가 있었고, 또한 방학중 진행되는 스터디에 참여 및 준비를 하느라 PS할 시간이 부족했다... 그래도 나름대로 PS를 아예 안한 것은 아니므로 시작하겠다.

 

1. Gröbner basis and Buchberger algorithm

다음의 글을 참조하라: https://infossm.github.io/blog/2025/01/31/Buchbergers-algorithm/

 

2. PS일지

2.1. https://www.acmicpc.net/problem/32233

티어가 높지 않은 것은 아마 완전히 정당한 추론을 할 필요 없이 충분히 신용할만한 추론들만으로도 AC를 받을만하기 때문인것도 있고, 이 사실들에 대해 잘 알고 있거나 알아낼 수 있다는 전제하에 큰 풀이의 흐름은 어렵지 않기 때문일 것이다. 여기에서는 이 문제에 사용된 중요한 사실들과 아이디어에 대해 설명한다.

 

Proposition. $R^2$에서, v-e+f=2.

 

Proposition. toroidal graph에 대해서, v-e+f=0.

 

Lemma 1. 정점이 n>=7개인 toroidal graph의 최대 간선수는 3n이다.

pf) toroidal graph에서도 마찬가지로, 하나의 면은 적어도 3개 이상의 간선을 포함해야 한다. 즉, 다음과 같은 부등식이 성립한다: $2e\le 3f,f\le \frac{2}{3}e$. 이를 상기하며 v-e+f=0을 정리하면, $0=v-e+f>=v-\frac{e}{3}$과 같은 식을 얻으므로, $e\le 3v$이다. 구성하는 방법은 다양하고, 가능한 것을 어렵지 않게 확인 가능하므로 생략하겠다.

 

Lemma 2. 정점이 n>=5개인 planar graph의 최대 간선수는 3n-6이다.

위와 동일하게 증명 가능하다.

 

Proposition 3. 위에서 n의 제한보다 작은 그래프들의 경우에는 clique들이 해당 그래프의 class 내부에 속한다(즉 ,K_7은 toroidal하고, K_4는 planar하다.).

 

이제, 위의 사실들을 조합해서 문제를 풀 수 있다.

 

결국, 잘 알려진 님게임의 성질에 의해 풀고자 하는 것은 $a_1,...,a_n$과 $b_1,...,b_n$이 있을 때, 각 인덱스별로 수열의 값을 하나씩 뽑아서 xor한것이 0이 되는지 판별하고, 가능하다면 구하는 문제로 환원이 가능하다. 이는 xor basis를 통해서 해결할 수 있다.

 

2.2. https://www.acmicpc.net/problem/21643

약 3개정도의 풀이가 있다. 전부 비슷한 논리를 사용한다.

2.2.1. 1차이나는 간선들을 이용해서 이동가능한 컴포넌트들중 가장 작은것을 고르자. 이를 C라고 한다면, e(V-C,C)에 속한 간선중 최솟값을 잡고, 그것에서 1을 뺀 값만큼 C 전체의 정점들에 더해준다. 이렇게 하고 나면 여전히 coloring이 proper함은 자명하고, 추가로 C는 인접하는 컴포넌트가 하나 늘어나게 된다. 작은걸 고르고 다른것에 합치는 연산을 반복하므로, 작큰의 논리를 적용하면 시복이 보장됨을 알 수 있다. 필자는 의문의 시간초과를 받아서 2.2.3으로 구현했다.

 

2.2.2. 그냥 2.2.1에서 C를, 1을 포함하는 컴포넌트로 하여금 간선을 잘 관리해주면 비슷하게 구현할 수 있다.

 

2.2.3. 위의 논리들을 극한까지 따지다보면, 다음과 같은 결론을 얻을 수 있다.

 

각 간선들을 2개의 유향간선으로 쪼개고, 각 유향간선 uv마다 c(v)-c(u)-1을 적는다. 이제 1번 정점에서 각 정점까지 최단거리를 구하고, 그 값만큼을 각 coloring에서 빼주면, 여전히 컬러링은 proper하고, 추가로 전체 컴포넌트가 연결임을 알 수 있다.

 

3. Ptz winter 2024 Day4

실제로 셋돌때는 I같은 경우에는 맞왜틀에 빠졌었다.

 

L. 간단한 문제. 중앙에 있는 원소를 기준으로 위쪽은 2를 곱해서 더해고, 아래는 2를 곱해서 뺀것이 답이 됨을 알 수 있고, 개수도 그러한 방식으로만 배열이 되도록 하는 배열개수를 잘 세어주면 된다.

 

H. 홀수일때는 안되는거같은데 왜 안되는지는 잘 안생각해봤다. 짝수일때는 사다리꼴 두개를 잘 합쳐서 구성하면 된다.

 

E. 셋을 돌때는 이게 굉장히 많이 풀렸는데, 그정도로 쉬운 문제인가싶다. 일단 나이브한 알고리즘을 생각해보면, 결국 관리해야 하는 값은 지금까지 쓴 줄의 총량이랑, 현재 줄에 있는 단어의 개수이다. 그런데, 다음 구간에 영향을 주는 유일한 인자는 단어의 개수이고, 이는 0~24까지의 값밖에 취할 수 없기 때문에 25개의 값 모두에 대해서 전이가 어떻게 일어나는지를 관리하는 세그를 짜면 된다.

 

F. 분할정복을 통해서, 다음과 같은 값을 출력하는 노드를 만든다:

 

(l,r,x): (l,r) 사이에 1인 값이 x개 이상 존재한다면 1, 아니라면 0

 

그렇다면, (l,r,x)=1일 조건은 어떤 k가 존재해서 (l,mid,k)가 켜져있고, (mid+1,r,x-k)가 켜져있음과 동치이다. 열심히 구현하면 맞는다.

 

M. 정해는 무척 길고 복잡해서 잘 모르겠는데, 나이브한 코드를 짜서 값을 찍어보면 규칙성을 찾을 수 있다(규칙성도 별로 아주 간단하지는 않다...)

 

I. 조건을 만족하는 팰린드롬은 두가지 타입으로 나눌 수 있다.

 

1. 팰린드롬의 중앙이 T 안에 있는 경우

2. 그렇지 않은 경우

 

1번 케이스의 경우에는, 뒤에 와야 하는 문자열을 결정할 수 있고, 추가로 팰린드롬의 중앙이 T 내부에서 0.5칸씩 이동하는 것을 생각했을 때, 뒤에 오는 문자열은 맨 앞에 문자가 하나씩 추가되는 식으로 변화함을 알 수 있다. 이를 전부 세기 위해서는 주어진 문자열 S를 반전한 것의 suffix array를 구성한 다음, 거기에서 적절한 이분탐색을 통해 문자열을 계속하여 탐색해나가며 그 개수를 관리해주면 된다. 개수를 더할지 말지는 결국 T의 특정 부분이 팰린드롬인지 판별하는 것을 요구하는데, 이는 해싱을 쓰면 된다.

 

2번 케이스의 경우에는, S 내부에 존재하는 모든 T의 반전에 대해서, 그 앞에 올 수 있는 팰린드롬의 개수를 전부 합쳐야 한다. 특정 위치를 끝으로 하는 팰린드롬의 개수는 매내처를 쓰든 해싱을 쓰든 어렵지 않게 해결할 수 있다. 참고로 필자는 매내처 쓰는법을 몰라서 항상 해싱을 쓴다. 이제 S의 suffixarray에서 T의 부분문자열에 해당되는 구간을 잡고, 그에 대해서 팰린드롬개수를 누적합을 통해 합쳐주면 된다.

 

4. 소감

최근에 상당히 바빠서 다음 포스팅이 나오기까지는 시간이 걸릴 가능성이 높다. 사실 이게 소감이라고 할만한건지 잘 모르겠다.