Syphon의 자기개발 일지

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

올해는 예선/본선 모두 온라인으로 진행되는 까닭에 조금은 아쉽지만, 그래도 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$이..

개강 이후 정말 바쁘게 살다가 정말 오랜만에 코포를 뛰었다. A: Orac and LCM 입력으로 들어온 숫자들의 pairwise LCM들의 전체 GCD를 구해야 한다. 예제 입력을 보고 조금 고민을 해 보니, $n$개의 숫자 중 최소 $n - 1$개에 포함이 되어있는 약수는 우리가 구하는 최종 정답의 약수가 되어야 한다. 입력으로 들어올 수 있는 수의 범위가 충분히 작기 때문에, 입력으로 들어온 각 숫자들의 약수들을 찾고, 각 약수마다 몇번 등장했는지 새로운 배열을 통해 세어주기만 한다면 최종 정답이 약수로 가져야 하는 모든 수들을 찾을 수 있다. 이제 방금 찾은 수들의 LCM을 구하면 끝이다. 사실 고민을 조금이 아니라 많이 했다. 구현 과정에서도 실수가 여러번 있어서 풀기까지 시간이 조금 걸렸다. ..

피곤한 날은 퍼포먼스가 확실히 떨어지는 듯 하다. A: Sum of Odd Integers 2분에 AC B: Princesses and Princes 구현 문제. 빠르게 구현하여 11분에 제출하였으나, 배열 초기화 작업이 $O(n)$인 것을 간과하여 $O(n^2)$ 코드를 제출하였다. C++로 바꿔서 구현하면서 시간만 더 뺐기고, C++ 솔루션이 TLE를 받고 나서야 문제점을 발견하였다. 이 문제만 아니었어도 레이팅이 올랐을 듯 하다. 3 TLE 이후 37분에 AC 9분 걸릴 문제를 35분 걸려서 푸는 마술 C: Game with Chips 얘도 별거 없다. 왼쪽 아래로 모든 칩을 몰아준 후 모든 칸을 방문하면 된다. $mn + n + m - 3 \leq 2nm$이 모든 자연수 $n$, $m$에 대해 성..

벌써 네번째 퍼플 진입이다. 다섯번째는 필요 없기를 바란다. A: Bad Ugly Numbers 혼자 생각을 너무 많이하고 어렵게 푼 것 같다. 7분에 AC B: Maximums 정의대로 하면 된다. 13분에 AC C: Permutation Partitions 주어진 permutation을 $k - 1$개의 칸막이를 설치함으로써 각각 perumutation에서 연속된 $k$개의 partition으로 나눠야 한다. 이때, 각 partition의 max값의 총합을 최대화하고자 한다. 최댓값은 무엇이며, 최댓값을 갖는 분할의 경우의 수는 몇가지인가? 어려운 문제인 듯 했으나, 최댓값을 최대한 키우기 위해서 어떻게 분할해야 좋을지 생각하는 순간 해답이 보였다. 최댓값을 키우기 위해서는 각 partition마다 ..

블루-퍼플 진동은 당분간 계속될 것 같다. 대회가 있는 줄 모르고 있었는데, Nyso의 카톡을 받고 추가 등록 시간에 등록하였다. A: EhAb AnD gCd 최대공약수와 최소공배수의 합이 $x$가 되는 두 수를 출력하면 된다. print(x - 1, 1)로 해결했다. 12분에 AC B: CopyCopyCopyCopyCopy 길이 $n$의 배열이 들어온다. 그 배열을 $n$번 반복시킨 새로운 배열에 대해서, LIS는? 처음에는 착각하여 답이 나올 리 없는 코드를 제출했었다. 다시 생각해보니 print(len(set(a)))로 한번에 처리되는 문제였다. 1 WA 후 18분에 AC C: Ehab and Path-etic MEXs Tree가 입력으로 들어온다. $n-1$개의 edge에 $0$부터 $n - 2$..