PS | CP

[18806] 와일드 카드

부제: Wildcard string matching with Fast Fourier Transform 문제 분석 우선 지문을 읽어봅시다. 길이 25만의 알파벳 소문자 + '$?$' + '$\ast$'로 구성된 문자열이 두 개 들어옵니다. 문제에서 제시한 조작으로 두 문자열이 '같도록' 하면 됩니다. 문제에서 제시한 조작(연산)은 세 가지로, 문자 삽입, 문자 삭제, 문자 치환입니다. 그런데 사실 연산이 셋이나 있을 필요가 없습니다. 그 이유는 문자 '$\ast$'의 성질 때문인데, 이 녀석은 모든 문자이면서 모든 문자열로 취급될 수 있기 때문에 '치환'과 '삽입'의 역할을 대체할 수 있고, 길이가 0인 문자열로 취급될 수도 있기 때문에 '삭제'의 역할을 대체할 수 있습니다. 따라서 가용 연산을 다음과 같이 간단하게..

[19499] K-transform

거꾸로 생각합시다. k-transform으로 만들어지는 수는 $k(k(k(...(k(1+a_0)+a_1)...+a_{n-1})+a_n$의 꼴($0\le a_n<k,a_0\ne k-1$)이고, 여기서 $\sum _{i=0}^n{a}_i+n=m$이 됩니다. 저걸 전개해버리면 $(1+a_0)k^n+a_1{k}^{n-1}+...+a_{n-1}k+a_n$입니다. 이걸 $k$진 수로 생각하면 $(1+a_0)a_1{a}_2{a}_3...a_{n-1}{a}_{n(k)}$, 그러니까 $\text{digit sum}+\text{digit}-1=m$인 모든 $k$진 수의 개수를 구하는 문제가 됩니다. 쉽지 않네요... 그렇죠? 애초에 제약 없이 수를 나누는 문제도 중복조합으로 풀어야 하는데.....

[18968] Circle Union

아마 1학기 기말고사 기간에 풀었던 걸로 기억하는 문제. 푼 지는 꽤 됐는데 언젠가 글을 써야지 써야지 하다가 이제서야 쓴다. covered region을 최대화하려면 각 원이 모두 한 점에만 만나야 한다. 그러니까 모든 원(과 원 안의 부분)을 이루는 점의 집합의 교집합의 원소가 정확히 한 개여야 한다는 것이다. 그렇지 않은 경우엔 원 하나를 적절히 움직여서 더 넓은 covered region을 갖는 형태로 만들 수 있다. 그러면 원점을 지나는 원들의 형태를 다루는 문제가 된다. 정확히는 형태라기보다는 원의 중심이 존재하는 위치? 각도? 그런 것이다. 이제 문제 상황을 좀 편하게 다루기 위해 도형을 극좌표계로 펼쳐 보자. 극좌표계에서 원점을 지나고 반지름이 $R$인 원은 $r = 2R\cos(\thet..

[17399] 트리의 외심

클래스 8에 속한 문제. sparse table, 혹은 LCA만 알고 있다면 간단한 케이스 분류로 쉽게 풀 수 있다. 한 트리 위의 노드 $a,b,c$를 생각하자. 두 노드 $x,y$에 대해 $x$에서 $y$로 가는 경로를 $P_{xy}$라고 적기로 하고, 이제 $P_{ab},P_{bc},P_{ac}$를 생각해 보자. 그럼 다음이 성립한다. 1. $P_{ab},P_{bc},P_{ac}$는 항상 유일하게 존재한다. 왜냐? 트리니까. 한 노드에서 다른 노드로 가는 경로가 여러 개 있다는 건 사이클이 있다는 소린데 그럼 트리가 아님. 2. 세 경로 $P_{ab},P_{bc},P_{ac}$에 모두 속해 있는 노드는 항상 한 개 이상 존재한다. 트리이기 때문. 만약 그런 노드가 없다면 $a \to..

[17378] 공의 합집합

x축에 타코야끼마냥 중심을 꽂힌 다양한 크기의 구들이 있는데, 이 녀석들의 전체 부피를 구해야 한다. 그런데 서로 겹치는 경우가 생길 수 있기 때문에 그냥 구해서는 안 된다. 뭔가 방법을 써야 한다. 우선 3차원 상황을 그대로 써먹으려고 하면 불편하다. 어차피 문제 상황의 모든 도형이 x축을 중심으로 한 회전체 꼴이기 때문에 2차원 평면 위의 반원들로 차원을 낮추자. 각 공 $S_i=(x-x_i{)}^2+y^2+z^2\le r_i^2$들은 이제 $C_i=(x-x_i{)}^2+y^2\le r_i^2(y\ge 0)$으로 생각하자. 그럼 부피는 간단하게 $\displaystyle \pi\int_{a}^{b} y^2dx = \pi\int_{a}^{b} \{r_i^2 - (x - ..

[16140] 정수론과 응용

가우시안 수 두 개 주고 GCD를 찾으라는 문제다. 3개의 subtask로 나누어져 있는데, 첫 번째는 새로운 차원을 사용하지 않는 정수 GCD, 두 번째는 아마도 좀 나이브하게 찾는(아니면 arctan 같은 걸 쓴다거나... 우웩.) 방식을 노린 것 같고, 마지막 subtask까지 전부 맞으려면 그보다는 좀 더 머리를 쓰는 방식을 요구하는 것으로 보인다. 우선 이 '가우시안 수' 라는 녀석을 살펴보자. 사실 그냥 복소수다. 이 가우시안 수 간의 곱셈은 다음과 같이 표현됨을 우리는 잘 안다. 두 복소수 $n=a+bi,m=c+di$에 대하여, $n\cdot m=(ac-bd)+(ad+bc)i$. 가우시안 수의 나눗셈에 대해 생각해 보자. 일단 가우시안 수를 서로 나눌 수는 있다...

[13334] 철로

13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 많은 블로그들에서는 Priority Queue를 사용하는 해설을 적어 놓았고 사실 Priority Queue를 쓰는 게 낫긴 한데, 여기서는 Priority Queue를 안 쓰는 방식을 소개한다. 문제의 철로 L의 오른쪽 끝과 수직선 상에 존재하는 가장 왼쪽의 건물이 처음 만날 때부터 왼쪽 끝이 가장 오른쪽의 건물을 지날 때까지 이동한다고 생각하자. 이 상황을 L이 움직임에 따라 각 건물이 L에 추가되었다가 제거..

[Div2 774] 3솔

15번째로 참여한 Codeforces Round #774 (Div. 2)에서 블루 퍼포를 따냈다. ABC를 솔하고 E를 파다가 실패했는데, 3솔만으로 퍼포가 나온 걸 보면 빠르게 푸는 게 꽤 큰 영향을 주긴 하나보다. D는 복잡할 것 같아서 대충 보고 때려치우고 그나마 친숙한 정수론 얘기 하는 E를 풀 계획이었는데 뭐가 문제였는지 자꾸 유사하면서도 다른 답만 뿌려대서 결국 못 풀고 마무리. 포함-배제를 잘못 짰는지... 오버플로우가 문제였는지... 그래도 일단은 지금까지 참여한 대회 중 최고 기록이고, 레이팅도 91이나 올랐으니 아쉬우면서도 만족스러운(??) 대회였다. 어떻게 풀 지는 잡았는데 구현을 시간 내로 못 해서 마지막 1솔을 놓치는 경우가 많았다. 기초적인 구현 속도를 좀 높일 필요가 있겠고, ..