Syphon의 자기개발 일지

Round 1, 2에 참여했으나 완전 망해버려서 기록을 남기기 귀찮아졌다. 그래도 참여를 하긴 했다는 기록 차원에서 연습지를 올린다:

자다 일어나자마자 Nyso의 연락을 받고 대회 레지스터. 초반 문제를 최대한 빨리 풀겠다는 마음으로 임했다. A: Suborrays 그냥 아무거나 출력하면 된다. 2분에 AC B: Fix You 젤 오른쪽 column과 젤 아래 row만 살피면 된다. 5분에 AC C: Cyclic Permutations Cycle이 생기는 조건을 먼저 찾아내고자 했다. 잘 생각해보니 permutation의 값들이 내려갔다가 올라가는 경우, 즉 $2, 1, 3$과 같은 배치인 경우 cycle이 생긴다. 이 두 조건이 동치인 것을 증명하기 전에 그냥 구현하고 제출해보기로 했다. 경우의 수를 세는 방법은 두가지가 있다. 직접 세주는 방법과 여집합을 이용한 방법이다. 여집합을 이용하는 경우, 값들이 올라가서 고점을 찍고 내려가..

여섯번째 퍼플진입. A: Rainbow Dash, Fluttershy and Chess Coloring 홀짝성 따져서 잘 해보면 된다. 6분에 AC B: Applejack and Storages 각 길이의 plank가 몇개씩 있는지 잘 세주면서, 4개 이상짜리 집합과 2개 이상짜리 집합으로 나눠서 관리하면 된다. 20분에 AC C: Pinkie Pie Eats Patty-cakes 예제 입력과 출력을 보니, 제일 빈도가 높게 등장하는 숫자가 critical한 것 같았다. 빈도가 제일 높은 숫자를 최대한 떨어뜨려 배치한다면, 나머지 숫자들은 적당히 배치하여 동일 숫자간의 최소 거리를 유지할 수 있을 것 같다는 강한 직관을 느꼈다. 강한 직관은 보통 맞다. 문제가 되는 부분은, 빈도가 제일 높은 숫자가 여러..

더 늦어지기 전에 본선 후기를 남긴다. 이미 뒷북 후기... 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$이..

드디어 Round 2다. 세번의 기회가 주어졌던 Round 1과는 달리 이제는 단판승부이기 때문에 정말 정신 차리고 필요한 모든 연료(?)까지 옆에 비축해두고 대회를 시작했다. 1. Incremental House of Pancakes There are two stacks of pancakes. The height of each stack is given as input. You are to serve customers. The $i$th customer requires $i$ pancakes to be served. $i$ pancakes will be given from the stack of higher height. If the two stacks are of equal height, the le..