leo020630의 블로그

6솔브, 39등으로 대회를 마쳤습니다. 타임라인 자세한 시간대가 생각나지 않아 대충만 정리하도록 하겠다. 우선, 컴퓨터로 한글인 문제들을 훑었다. E가 쉬워보였고, 가장 먼저 풀이를 찾은 qjatn0120 선배가 짜서 맞았다. 이후 문제지가 도착해 slah007 선배는 A, qjatn0120 선배는 C, 나는 K를 잡았다, A와 C는 무난히 맞았지만, K는 다익스트라가 돌 것이라 생각한 나의 오판으로 TLE를 몇 번 받았다. 이후 DAG임을 깨닫고 DP를 짰지만, 이 역시 TLE를 받았다. 결국 G를 풀고 온 qjatn0120 선배가 받아서 AC. F 역시 slah007 선배가 TLE를 계속 받아 qjatn0120 선배가 새로 짜 AC를 받았다. 이후 1시간 가량 나와 qjatn0120 선배는 J, sl..

A. Ela Sorting Books (0:15, +2) 각 묶음에 대해 Mex 이후로는 무슨 알파벳이 들어오던 상관이 없다. 따라서 앞 묶음부터 앞 알파벳을 하나씩 넣어주는 것이 항상 최적이다. 구현을 약간 이상하게 해 2번 틀려서 B 풀고 다시 와서 풀었다. B. Ela's Fitness and the Luxury Number (0:13, +) 각 \(a\)에 대해 \(\lfloor\sqrt{x}\rfloor = a\)인 \(x\) 중 \(a\)의 배수는 3개 \( (a^2, a^2+a, a^2+2a) \)이다. 이 사실을 이용해 잘 구해주면 된다. sqrt 함수를 쓰면 틀린다는 얘기가 많은데, 나는 그냥 맞았다.. 왜지? C. Ela and Crickets (0:42, +2) 대충 해보면, 우물 정..

공휴일에 좋은 대회가 있길래 팀 연습을 했다. 내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다. 세팅 문제 때문에 5분쯤 늦게 시작했다. ~0:32 slah007 선배는 D, 나는 J, qjatn0120 선배는 H를 봤다. 가장 먼저 코딩에 들어간 H를 27분에 AC받고, 쉬운 문제였던 D 역시 32분에 AC가 나왔다. 나는 J를 보다 어려워서 던진 후 많이 풀린 B로 넘어갔다. ~1:08 B에서 끙끙대다 qjatn0120 선배가 핵심적인 관찰을 해 주셔서 바로 코딩에 들어갔다. 무지성으로 세그를 짠 뒤 mod 이슈로 한 번 틀린 후 B를 맞았다. ~2:27 이후 A, J, E의 코딩이 번갈아서 진행되었다. J는 사풀인걸 알지만 코딩이 짧아 qjatn0120 선배가 ..

주말에 노느라 ABC, ARC를 다 안쳐서 죄책감에 이거라도 쳤다. A. Working Week (0:12, +) 잘 정리하면 답은 \(\frac{n}{3} - 2\)라고 한다. 난 생각이 안나서 더럽게 풀었다. 이걸 어떻게 알지? B. Tea with Tangerines (0:16, +) 최솟값이 기준이 되어야 한다는 사실을 자명하게 알 수 있고, 다른 수들도 잘 나눠줄 수 있다는 사실은 덜 자명하지만 찍어서 맞출 수 있다. C. Phase Shift (0:35, +1) 그리디하게 보내주면 되는데, 모든 알파벳이 반드시 하나의 큰 사이클을 이루어야 해서 좀 까다롭다. 난 대충 Union Find를 써서 구현했다. D. Meta-set (0:47, +) 2개를 정하면 남은 1개를 정할 수 있다. 따라서,..

팀 연습이 끝나고 Rated 코포가 있길래 오랜만에 쳤다. A. Glory Addicts (0:06, +) 잘 번갈아서 하는 것이 최적이다. 정렬한 후 큰 것 부터 써주면 되는데, A번 치고 케이스 워크가 좀 있는 편이라 어려웠다. B. Prefix Sum Addicts (0:14, +) \(N=K\)일 때는 배열을 만들 수 있으므로 단조증가인지 판별하면 되고, \(K=1\)일 때는 항상 가능하다.이를 잘 접목하면 그렇지 않은 상황에서도 만들어진 배열이 단조증가인지 판별하고, 만들어진 배열의 첫 항을 잘 만들 수 있는지 판별하면 된다는 사실을 알 수 있다. C. Even Number Addicts (0:38, +1) 수가 무엇인지는 중요하지 않고 홀짝성만이 중요하다. 제한이 작으므로 홀수의 개수와 짝수의..

3인 5시간 셋을 2인 3시간으로 쳤다. 셋은 BAPC 2019를 사용하였다. 내가 뒤, slah007 선배가 앞을 보고 시작했다. ~0:07 브론즈 문제인 J와 B를 풀었다. J는 안쓰던 컴이라 괜히 int 썼다가 오버플로우로 한 번 틀렸다. ~0:30 H AC를 받았다. \(10^8\)짜리 풀이인데 63ms에 돌아서 신기했다. ~0:50 slah007 선배가 오래 잡고 있던 E를 맞았다. 약간 귀찮은 DP인 것 같았다. ~0:55 slah007 선배의 E와 번갈아 내가 코딩을 하던 A를 맞았다. ~1:08 그리고 F를 봤는데 많이 본 유형이라 그냥 슥슥 풀었다. slah007 선배는 귀찮은 구현 문제인 G를 잡았다. ~1:57 slah007 선배가 G를 맞았다. 나는 I, K, L를 잡고 있었는데, ..

이번 여름, 4연속으로 진행했던 대회 운영의 마지막을 장식한 PPC이다. 사실 시작은 제일 먼저 했다..ㅋㅋ 할 말이 무척 많으나, 글에서 하나씩 풀도록 하겠다. 대회 링크 : https://www.acmicpc.net/category/detail/3186 에디토리얼 : https://www.acmicpc.net/board/view/100196 발단 및 출제 과정 PPC에는 몇 가지 대회 규정이 있는데, 그 중 하나가 "모든 참가자는 전년도에 수상한 상보다 높은 상만을 수상할 수 있다." 라는 규칙이다. 나는 작년 대회에서 1등을 했기에 출전을 할 수 없었고, 자연스럽게 출제진으로 빠지게 되었다. 사실 저 룰이 없었더라도 양심상 나가지 않았을 것이다. 여튼, 그렇게 21년도 출제진에서 hyperbolic..

이번 여름 4연속으로 있는 대회 운영 참여 중 3번째로 진행된 KAUPC에 대한 후기이다. 하루에 백준 홍보게시판을 3번씩 확인한 덕분에 선착순 검수진 모집을 잡을 수 있었다. PPC와 일정이 겹쳐 엄청나게 많은 시간을 투자하지는 못했고, 많은 시간 정도만 투자했기에 문제별 후기와 총평정도만 간단히 적을 예정이다. 대회 링크 : https://www.acmicpc.net/category/detail/3184 문제별 후기 A. Triathlon 무난한 A번 문제이다. 지문이 좀 어지럽긴 한데, A번이라 별 상관은 없는 것 같다 B. 자바의 형변환 처음 봤을 때에는 여러가지 불명확한 부분이 많았는데, 깔끔히 정리해 평범한 트리 탐색 문제가 되었다. 문제 자체는 적당히 교육적인 BFS 문제이다. C. 캔 주기..

https://leo630.tistory.com/92 이 글에서 이전 년도 PPC 문제들 풀이를 작성하기로 했었는데, 올해 대회가 3일 후이기 때문에 우선은 2018년도 대회 풀이를 써보려 한다. 2019년 대회는 쓰지 않을 예정인데, 아직 다 풀지도 않았고 + 뭔가..뭔가인 문제들이 좀 있고 + 무엇보다 에디토리얼이 있길래 생략하도록 하겠다. 우리 학교 대회인 만큼 평소 쓰던 풀이들보다는 정성들여 써보도록 하겠다. A. Caesar Cipher 문제 소재로 자주 등장하는 카이사르 암호인데, 다른 문제들에 비해 까다로운 부분이 몇 군데 있다. 1. $k$의 크기가 크다. 이는 어떤 알파벳을 26번 밀면 다시 돌아온다는 것을 이용해, $k$를 26으로 나눈 나머지를 취한 후 진행해도 똑같은 결과를 얻을 수..

쓸 내용이 많이 없어 간략히만 적도록 하겠다. 타임라인 ~0:44 여느 년도와 마찬가지로 1번은 꼭 풀고 가야 할 문제라고 생각해 우선 1번을 열심히 풀었다. 풀이는 잘은 기억나지 않지만 변수 분리를 해 set으로 잘 관리해주면 풀 수 있었던 것 같다. ~0:56 이후 2번을 봤는데, 풀테는 잘 모르겠고 우선 \(O(N^3)\) 섭테 먼저 긁었다. 이후 이상한 최적화를 몇 번 하다 3번으로 넘어갔다. ~1:22 3번을 좀 생각했는데 2번 섭테부터는 시간이 좀 필요할 것 같아 1번만 긁고 다시 2번으로 돌아갔다. ~4:00 4번, 5번도 잠깐 봤지만 별 생각이 안나 다시 2번으로 돌아왔다. 2시간 반 쯤 지났을 때 2번의 핵심적인 관찰 하나를 해냈고, 세그트리를 \(N\)개 만들면 \(O(N^2 logN)..