dlwocks31의 PS일기장

https://www.acmicpc.net/problem/20967 20967번: Uddered but not Herd A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might be different www.acmicpc.net USACO 2021 January Contest > Gold 1번으로 출제된 문제이다. 풀이 제한을 자세히..

https://www.acmicpc.net/problem/20649 20649번: Stuck in a Rut The first line of input contains $N$. Each of the next $N$ lines describes the starting location of a cow, in terms of a character that is either N (for north-facing) or E (for east-facing) and two nonnegative integers $x$ and $y$ ($0\le x\le 10^9$, $0\le www.acmicpc.net 방향이 다른 모든 cow pair에 대해서, 다른 소의 간섭이 없을 때 두 개의 소가 충돌하는지, 충돌한다면 예상 충..

올해는 병특으로 근무중이여서 재학생이 아니기 때문에 어처피 본선은 못 나가고, 작년 Little Piplup 팀에서 나랑 같은 휴학생 처지가 된 Coffeetea, Diordhd와 한 팀을 꾸려서 나가게 되었다. 결과는 생각보다 괜찮았던 7솔브! 비록 A랑 J가 풀만했지만 풀지 못했던 게 조금 아쉽긴 해도, 대회 중에 문제 솔루션이 끊임없이 나왔고, 구현도 큰 코딩 실수 없이 생각했던 걸 (J 빼고) 모두 빠르게 구현해내서 좋은 결과를 얻을 수 있었던 것 같다. 대회 중 역할분담은 주로 Coffeetea와 Diordhd가 솔루션을 생각해서 전달해주고, 그걸 내가 받아서 구현하는 방식이였다. 우리가 푼 문제 한정으로 솔루션은 koosaga.com/262 와 대략적으로 일치해서, 여기서는 솔루션을 자세하기 ..

정말 오랜만에 하루종일 PS했다. 결과는 그렇게 맘에 들지는 않지만, 그래도 오랜만에 PS를 스릴있게 한 것 같다.다만 1년 전과 달리 실력이 별로 늘어난 느낌이 들지 않아서 좀 슬펐다. 1년 전에는 지금의 나는 SCPC예선쯤은 여유롭게 통과할 줄 알았는데, 역시 지난 1년간 PS 열심히 안한게 티난다..ㅋㅋㅋ 매우 아슬아슬한 점수인데 과연 본선 진출할 수 있을까? 1 - 실력 맞추기 (13:10 AC) 일단 두 개의 같은 길이의 배열 \(a_i\), \(b_j\)가 있고 1:1매칭을 해서 \(abs(a_i - b_j)\) 의 합을 최소화하는 문제인데, 대신 하나의 \(a_i\)를 임의의 숫자로 수정할 수 있는 문제이다. 기본적으로 아무 수정을 하지 않는다면 그냥 정렬하고 같은 인덱스끼리 매칭하면 되는데..

https://www.acmicpc.net/source/share/412dd80e9e794587a5a0f3b851164ff7 공유 소스 보기 www.acmicpc.net KMP로 모든 string마다 suffix와 prefix가 같은 suffix/prefix의 길이를 찾을 수 있다는 생각을 했는데, 답을 빠르게 찾는데는 큰 도움이 되지 않았다. 생각이 안나서 결국에 공식풀이를 봤는데, 매우 신기한 방법이 있었다. 이 문제에서 a가 b와 이어질려면 a가 b의 prefix이면서 suffix이여야 한다. 이 때 suffix 조건을 제거해보자. prefix만 본다면 이 문제는 trie로 어렵지 않게 풀 수 있다. 각 노드마다 (이 노드에서 끝나는 string이 있다면)이 노드의 string에서 끝나는 최적의 답..

https://www.acmicpc.net/category/detail/2054 UCPC 2019 www.acmicpc.net 17등! 개인적으로는 그냥 딱 우리 실력에 풀 수 있는 걸 다 푼 느낌이였는데 생각보다 높은 순위를 받았다. 이번 셋이 워낙에 어려웠고 5솔 표준 세트였던 ABEKL중에서 A, E가 정말 말리기 쉬운 문제였기 때문에 그런 듯 하다. 타임라인: 0분: 시작할 때 gyuni가 ABCD, 내가 EFGH, nevivurn이 IJKL을 맡기로 했다. 우선 난 E의 페이지수를 보고 바로 빡구현문제라 판단해 일단 넘어갔고, F는 미친기하의 냄새가 나서 도망갔다. 7분: (현장 사진)"어 이거 그냥 트리 대충 그어보면 나오지 않을까?" 하고 G번에 뭔갈 적고 있는 dlwocks31. 아니였다고..

https://codeforces.com/contest/1198/standings/participant/26799422#p26799422 A - array의 distinct value한테만 비트를 배정해야 한다는 걸 못봐서 한번, 바이너리서치하는 배열을 정렬 안해서(..) 한번 틀리고 그걸 발견 못해서 B 풀고 와서 좀 더 직관적인 좌표압축? 코드를 짜서 맞았다. B - 온라인으로 풀면 레이지 세그를 써서 2번 쿼리를 레이지하게 뿌리면 된다. Div1B에겐 오버킬이였고, 정해는 오프라인으로 1번 쿼리들마다 앞으로 올 2번 쿼리의 값의 최댓값으로 바꿔쓰는 식. 너무 복잡하게 생각한 듯 하다. 나중의 2번 쿼리가 앞에 있는 어떠한 1번 쿼리든지 덮어씌울 수 있는 포텐셜이 있다! 식으로 접근하면 이런 풀이에 ..

아직 병특 3년+학교 2년이 남아 있어 SCPC에 올해 빼고도 5번은 더 참가할 수 있는데 수상기회는 2번밖에 없어 그냥 최대한 편하게 할려고 했다. 상 탈 수 있으면 좋은거고 못타면 내년에 더 잘할 때 더 좋은 상 타는거고.. 결과적으로는 616점으로 커트라인에 걸려서 바라는 대로 수상하지 못했다(?). 내년을 노린다..! A - 예선 A번으로 나왔어도 적당한 난이도 같다. 딱히 할 말은 없다. B - 좌표평면에 점들이 주어지고 그 점들을 잘 이어 단순다각형을 만드는데 그 단순다각형의 둘레를 최대한 크게 만드는 최적화 문제. 나는 컨벡스헐 만들때 쓰는 그 좌표정렬을 하고 순서대로 이어서 193점을 받았다. 공식 풀이가 꽤 재미있었는데, lower convex hull을 하나 만들고 남은 점들을 x좌표가..