본문 바로가기

ps 일기

 (11)
연습 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..
solved.ac Master 달성 군생활 목표 중 하나였던 'solved.ac master 달성'에 성공했다! 처음에 군대 들어갈 때만해도 다이아 푸는 것도 힘들어했는데, 1년만에 루비를 50문제나 풀게 될 줄은 몰랐다. 앞으로도 열심히 ps를 해야겠다. master 달면서 어려운 문제들을 많이 풀었으니 이제는 덜 어려운 문제들을 빠르게 푸는 연습을 해서 저점을 높여야겠다.
[1, 2, 3월] 군대에 간 덕분에 시간이 남아돌았다. 남는 모든 시간을 ps에 쏟아부었더니 루비 5와 다이아 1을 엄청 풀게 되었다. 푼 문제도 많으니 기억나는 문제들만 간략하게 정리해보자. 아직 코딩을 한 문제도 안 했다. 경찰과 도둑은 SCPC 2022 2번에서 했던 이분탐색을 비슷하게 트리에서 하면 되는 것 같은데 D2가 박혔다. 들려오는 소문으로는 구현이 어려워서 그렇다고 하더라. 과일 게임의 토픽은 이미 usaco에서 99번 우려져서 난이도를 보기 전에는 쉬운 문제일 줄 알았는데 생각보다 안 풀려서 쩔쩔맸다. 평균 최대화는 적당한 비빔밥인 것 같다. 아직 코딩을 안해서 내 풀이가 맞는지 잘 모르겠다. 뚫기는 timeismoney와 같은 아이디어로 접근하면 쉽게 풀렸다. 몇몇 루비들은 풀이를 까는 것이 도움되는 ..
[12월] 사실 시험기간이라서 ps를 조금 쉬었다. 매일매일 하던 게임도 한달간 안 했으니 ps 정도는 쉬어도 되는거로 하지만 시험기간이 끝나고 심심해서 ps를 조금 했다. 푼 문제들을 알아보자. 난이도가 쉬운 대회면 검수가 쉬울 줄 알았다. 하지만 난이도가 낮은 만큼 뽑는 검수 인원도 줄어들어서 검수날먹을 할 수 없었다. 모든 검수진이 모든 문제를 검수했다! I번의 풀이를 새로 만들었다! 원래 문제가 조금 잘못된 면이 있어서 고쳐서 예쁜 문제로 만들었다. 다이아쯤 찍힐 줄 알았는데 내가 풀 때 문제 조건과 현재 문제 조건이 달라서 티어가 조금 내려간 것 같다. 그리고 뚫리기도 했다. 1달간 ps를 쉬고 재활겸 유사코 골드 한 셋 풀었다. 모든 문제가 생각보다 쉽게 풀렸다. Strongest Friendship G..
[11월] 일본 문제들 덕분에 조금이나마 ps를 하고 사는 것 같다... 무슨 문제를 풀었는지 알아보자. 쉽지 않다. P2이고 OI 문제인데 꽤 시간이 오래 걸렸다. 3차원 뇌가 안 돌아가나보다. 예전에 stock prediction이라는 icpc 문제도 못 풀었는데, 3차원에 약하다. 아마 3차원 문제라면 스위핑을 사용할 것이라고 생각했기 때문에 오래 걸리지 않았나 싶다. 이 문제에 대해서 한 가지 더 말할 것이 있는데, 자료구조 근육으로도 풀린다. 나 역시 약간의 자료구조 근육으로 이상하게 돌아가서 풀었다. 역시 근육은 있으면 좋은 것 같다... 내가 출제한 문제인 HLD랑 같은 아이디어를 사용한다. 날먹했다. 쉽지 않다. 풀이 떠올리기는 나름 쉬운데, 구현을 조금 돌아가서 했기 때문에 TL이 좀 빡빡했다. 직..

티스토리툴바