본문 바로가기

전체 글

 (49)
250626 연습 1. https://www.acmicpc.net/problem/32512구사과님의 잘 비벼진 문자열 비빔밥이다. failure function으로 만든 트리에 대한 고찰이 잘 녹아있다. 문제는 그냥 잘 풀어서 풀이 생략. 중간에 모든 i에 대해 B[i..m]과 C의 longest common prefix를 구할 일이 있었다.나는 해싱이분탐색을 썼다. 해싱 소수에 const를 안 붙였더니 시간이 많이 걸렸다. 선형로그 시간복잡도이다. C[i..len(C)]와 C의 longest common prefix를 Zc, B[i..m]과 C의 longest common prefix를 Zb라고 하자.Zc는 Z 알고리즘으로 구할 수 있다.i=1부터 m까지 스위핑을 해서 Zb를 구하자. i+Zb[i]가 최대인 경우의 i와..
250619 연습 1. 2025 Latin America Championshipserin, SongC, 나 이렇게 한 팀으로 한 첫 팀연습이다. 여기에서 확인할 수 있다. H번은 기본적으로 이 문제 와 같은데, 2개의 단계가 아니라 3개의 단계로 이루어져 있는 것이다. 풀이의 기본적인 맥락은 비슷하지만, 단계의 개수가 커지면서 casework가 늘어난다.이때 분할정복을 사용하면 인생이 편해진다. 어디에서 변화가 일어나는지 정확하게 알 필요 없이, '왼쪽 / 오른쪽에서 +x만큼의 변화가 나타난다' 와 같이 간단하게 나타낼 수 있다. 세그먼트 트리 노드 합치는 감성으로 하면 된다. 나는 분할정복 할 생각을 못해서 그냥 케이스워킹을 열심히 했다. 심지어 정해보다 케이스워킹을 999배 더 해서 구현하는데 힘들었다. J번은 구껍질..
Suffix automaton으로 Suffix tree 만들기 sa + lcp로 만드는 것과 무엇이 다를까아무튼 만들었으니 된거다.Suffix automaton 코드는 구사과님 코드에서 따왔다. + 250627 주석 추가#define sz(v) (int)v.size()#define fi first#define se second#define pii pairconst int mxA = 26; // 문자 개수struct SuffixTree /* 0번 정점은 루트 노드, 부모는 -1 i번 정점은 s를 1-base로 보았을 때 s[i..n]가 끝나는 위치(깊이가 모두 달라서 겹칠 우려 없음) child[i]에 i번 정점의 자식 vector i번 정점의 parent는 sa[i].slink rng[i]는 i번 정점과 부모를 잇는 substring에 대응하는 구간 (s[rng[i..
250606 연습 1. https://www.acmicpc.net/problem/31598N범위 10^6, 소인수 개수를 P라고 할 때 O(PNlogN)에 짧은 구현으로 풀 수 있다. 시간제한이 5초라서 널널할텐데 괜히 N범위에 쫄아서 O(PN)에 짰다. 일정 길이 구간 최솟값을 구해야 되는데, 스위핑으로 하면 편한 걸 스위핑으로 안 해서 구현이 길어졌다. 2. https://www.acmicpc.net/problem/31603정점 x에 대해 k번째 lca를 구해야 된다. m 이하의 조상 v에 대해 sub[par[v]] - sub[v]의 합이 k 이하인 m을 구해야 한다. pst로 range update + point query로 구현했다. (segtree 배열은 ett 인덱스 순) 그런데 정점에 쓰여있는 번호 순으로 s..
[KTST 2025] 뗏목 문제 링크 문제 설명높이 $h$, 너비 $d$의 직사각형을 $(h, d)$이라고 하자. $A$에서 얻은 직사각형 $(h_1, d_1)$과 $B$에서 얻은 직사각형 $(h_2, d_2)$를 조합하면 $\min(h_1, h_2) (d_1+d_2)$의 안정성을 얻는다. $A$ 혹은 $B$에서 원소를 사용하지 않는 경우, 해당 직사각형은 $(\infty , 0)$으로 간주한다.더보기다음을 만족하는 $(h, l, r)$을 수열 $X$의 maximal rectangle이라고 하자. 1. $h = \min(X_l, \cdots, X_r)$2. $X_{l-1}, X_{r+1} Maximal rectangle의 높이/너비만 나타내는 경우에는 $(h, d)$로 쓰고, 높이/왼쪽 끝/오른쪽 끝을 나타내는 경우에는 $(h, ..
solved.ac Master 달성 군생활 목표 중 하나였던 'solved.ac master 달성'에 성공했다! 처음에 군대 들어갈 때만해도 다이아 푸는 것도 힘들어했는데, 1년만에 루비를 50문제나 풀게 될 줄은 몰랐다. 앞으로도 열심히 ps를 해야겠다. master 달면서 어려운 문제들을 많이 풀었으니 이제는 덜 어려운 문제들을 빠르게 푸는 연습을 해서 저점을 높여야겠다.
2024 KAIST 14th ICPC Mock Competition 문제 출제 후기 조금 늦었지만 이번 카이스트 가을대회에 출제한 문제들의 비하인드를 이야기해보자 한다. 1. Same segment원래 골드 문제를 위한 문제였다. 가볍게 풀 수 있는 문제를 생각하기 위해서 익숙한 토픽들을 여러 개 훑는 중에 "주어진 구간 몇 개의 합이 자연수 K로 같은 음이 아닌 정수의 수열"이라는 토픽이 떠올랐다. 포함관계에 있는 구간이 없으면 그리디하게 앞에서부터 K/0을 채우면 되고, 포함관계에 있는 구간이 존재한다면 두 구간의 차집합에 0을 채우면 되는 아주 쉬운 문제였다. K가 답에 영향을 미치지 않는다는 아이디어도 괜찮아서 다항시간 풀이를 떠올리면 문제를 풀 수 있도록 N 이 문제를 발전시키기 위해 포함관계에 있는 두 구간의 차집합에 0을 채우는 과정을 더 빠르게 할 수 없을까 생각했지만, ..
색종이 붙이기 문제 링크 1. $N, M \leq 400$ 모든 칸을 다 덮을 수 있는 색종이의 집합을 $S$라고 하자. 각 $w$에 대해서 $(w, h) \in S$인 $h$의 범위는 $h \leq f(w)$의 형태로 나타난다. 이때 $f(w)$는 $w$에 대한 감소 함수이다. 따라서 $(w, h) \in S$를 판별하는 결정 문제를 $O(N+M)$번 해결해주면 해당 문제를 해결할 수 있다. 이 문제는 prefix sum을 이용해서 $O(NM)$에 쉽게 해결할 수 있다. 2. Maximal rectangle에 대하여 Maximal 직사각형이란, 내부에는 칠해진 칸이 없고 해당 직사각형을 포함하는 직사각형은 내부에 칠해진 칸이 있는 직사각형을 의미한다. 다시 말하면 직사각형의 각 변의 테두리에 칠해진 칸이 있는 직사각..

티스토리툴바