Syphon의 자기개발 일지

더 늦어지기 전에 본선 후기를 남긴다. 이미 뒷북 후기... A: 전단지 돌리기 짧은 문제 description이었지만, 거리 $D$ 이하의 모든 노드에 전단지를 돌릴 수 있다는 말이 무슨 뜻인지 이해가 되지 않아 반복해 여러 번 읽어야 했다. 결국 가볼 필요가 없는 노드들을 찾아내기만 한다면, 나머지 노드들을 전부 포함하는 subtree의 모든 간선 길이를 왕복으로 지나가게 되므로, 간단하게 정답을 구할 수 있다. 갈 필요가 없는 노드들을 제외하는 동시에 필요한 간선 길이들을 세기 위해서, 모든 leaf node로부터 출발하여 루트(출발지)를 향해 거꾸로 올라오며 거리 $D$ 이상 올라온 시점부터 간선들의 길이를 더해주기 시작했다. 같은 간선을 두번 세 주지만 않으면 된다. 파이썬으로 풀었다. B: 던..

백준 15902번 문제 Split and Merge는 UCPC 2018의 예선대회 문제로, 작년에 우리 팀이 UCPC 2019를 준비하는 과정에서 연습삼아 본 문제 중 하나이다. 팀연습 시간에 풀어내지 못한, solved.ac 기준 다이아 5의 난이도를 가진 어려운 문제이다. 결국 나는 이 문제를 새벽 내내 붙잡아 풀어냈었다. 문제는 내가 왜 맞는지 알 수 없는 방법으로 문제를 해결했다는 것이다. 그래서 당시에 1. 내가 문제를 푼 방법을 기록하고자, 또 2. 그 방법이 왜 작동하는지를 증명하고자 하였으나, 계속 미루다가 결국 1년이 지난 오늘에서야 코드를 다시 열어본다. 그래서 지금 작년의 내가 짠 코드를 보고 있는데, 이를 해석하려면 조금 시간이 걸릴 것 같다... 드디어 코드 해석을 마쳤다. 작년에..

올해는 예선/본선 모두 온라인으로 진행되는 까닭에 조금은 아쉽지만, 그래도 1년 전 [Syphon/Nyso/MathAmp] 팀이 출발하게 된 계기가 된 UCPC이기에 올해도 기대와 함께 출발하였다. 올해 우리의 팀명은 이다. 너무 잘 지은 것 같아서 만족스럽다. 솔직히 말해 작년의 팀명은 기억하기에는 너무 길었던 것 같다. 대회 시작 전부터 백준 서버가 터져서, 본선 진출 조건이 "4 솔브 팀 전부"로 완화되었다. 아쉽게도 긴장감이 다소 떨어지는 대회가 되어버렸다. J를 제외한 문제 5개는 대회 문제지를 받아본 3시부터 6시 반까지 3시간 반 동안 설렁설렁 풀었다. 결국 J는 내가 밤에 구현하여 제출했다. 그럼 이제 문제 설명 시작..! A: 수학은 비대면강의입니다 Trivial. 보자마자 나와 Math..

보호되어 있는 글입니다.

졸리지만 대회 시작. A: Common Subsequence 생략. 4분에 AC B: Sequential Nim 새로운 pile에서 take하는 사람이 주도권이 있다. 현재 pile에서 하나만 남기고 모든 stone을 가져감으로써 다음 pile을 다시 자기 차례에 가져갈 수도 있고, 현재 pile을 전부 다 가져감으로써 상대방한테 다음 pile을 넘길 수도 있다. 단, pile에는 두개 이상의 stone이 있어야 한다. 하나의 stone만 있는 pile의 경우, 무조건 그 하나의 stone을 가져가야 하며 차례는 상대에게 넘어간다. 시작 이후 크기 1짜리 pile이 몇개 연속되어 나타나는지를 살펴 그 홀짝성을 바탕으로 판별하면 된다. 단, 오직 크기 1짜리 pile만 있다면 승패 조건이 반대로 뒤집힌다...

지난 대회가 끝나자마자 레지스터했던 대회이다. 그때 레지스터해두지 않았다면 귀찮아서 하지 않았을 것 같다. A: Sign Flipping 문제 착각해서 뻘짓하다가 정신 차리고 홀짝성에 맞춰서 부호 부여. 5분에 AC B: Neighbor Grid 그냥 꽉꽉 채워주면 된다. 네 귀퉁이는 2, 네 모서리는 3, 나머지 값들은 4로 만들어 줄 수 있는지만 확인하면 된다. 근데 이 간단한걸 잘못 짜서 디버깅하면서 시간 다 버렸다. 4 WA 후 26분에 AC C: Element Extermination 지난 대회의 문제가 떠오르면서 이 문제 또한 greedy일 것이라는 느낌을 받았다. 삽질을 엄청 했다. 처음에는, 자료를 deque에 넣어 양 끝에서 greedy하게 두개씩 pop하고, 왼쪽 끝에서는 둘 중에 작은..

언제나 그랬듯이, 코포를 들어갔더니 대회가 있길래 register했다. A: Magical Sticks 앞 뒤로 짝지어 더해야 하는 줄 알았더니, 밑에 예시를 보니 가장 큰 숫자에 맞춰서 나머지들을 앞뒤로 더하는 것이었다. 4분에 AC B: Magical Calendar 진짜 오래 고민했다. 경우를 엄청 많이 나눠서 생각하고 실수에 실수를 더하다가, 결국 꽤나 간단한 정답에 도착했다. 그냥 경우 나눠서 해보면 별로 어렵지 않게 답이 나온다. 31분에 AC C: A Cookie for You 2번 유형의 사람들이 문제가 되므로, 이들에게 우선 최대한 많은 cookie를 주면 된다. 1번 유형의 사람을 중간에 어떻게 섞든간에 상관없이, 2번 유형의 사람은 처음 시작할 때의 두 cookie 종류 중 더 적은 ..

거의 종강일이 다 되어서야 코포를 다시 하게 되었다. 이번에도 정말 오랜만이다. A: FashionabLee 정 n각형에서 서로 직각인 두 변이 존재하는지 판별하는 문제이다. 단순히 n이 4의 배수인지 확인하면 되는 문제이지만, 내각의 합이 어떻고 배수가 어떻고 한참 따지고 있었다. 식마저 잘못 풀어서 더 많은 시간을 낭비하다가 결국에는 맞는 코드에 도달했다. 9분에 AC B: AccurateLee 이진문자열에서 $1$ 이후에 $0$이 연달아 나올 때, 둘 줄 하나를 지우는 연산을 반복할 수 있다. 주어진 이진문자열을 최대한 짧게 만드는 것이 목표이다. 문제를 푸는 데에 첫 열쇠가 된 insight는 $10$이나 $111...1110$이나 $1000...000$이나 $111...111000...000$이..

보호되어 있는 글입니다.

보호되어 있는 글입니다.