Syphon의 자기개발 일지

고등학교때까지만 해도 항상 수첩을 들고다니며 이런 저런 생각과 고민, 다짐들을 담아냈었다. 대학교에 와서도 이를 위해 새 수첩을 마련했지만, 고등학교때처럼 항상 옆에 지니고 있지 못해서인지 기록의 빈도가 처참하게 줄어들었다. 하지만 생각을 글로 적어내는 것은 꽤 큰 도움이 되고, 2020년은 그러한 도움이 많이 필요한 해인 것 같다. 새로운 수첩이 필요하다. But I still like to write with pen on paper. I guess I'll just do both. This can be for a more documental purpose - like a journal. My pen-and-paper notebook can still remain undeprecated - there'..

드디어 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..

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

작년의 코드잼에서는 Round 1A를 놓치고, 1B를 늦게 참여해서 결국 1C에서 779등으로 Round 2 진출에 성공했었다. 올해는 지난 1년간의 발전이 있었던 만큼, 첫 Round 1 대회에서 진출을 기대해보았다. Round 1A 링크이다. 1. Pattern Matching Question Wildcard character인 *가 포함된 문자열들이 입력으로 들어온다. 입력으로 들어온 모든 패턴들을 동시에 만족시키는 문자열을 찾아 출력하면 된다. Solution 예제 입력에 주어진 패턴들이 모두 *로 시작하고 알파벳으로 끝나는 형식(e.g. *abc)이길래, asterisk 기준으로 문자열을 분할했을 때 가장 앞과 뒤에 남는 'prefix'와 'suffix'에 우선 집중하기로 했다. Suffix 만..

코드잼이 돌아왔다는 뜻은 나의 CP 커리어가 만 1년이 되었다는 뜻이다 ㅎㅎ QF 라운드 링크이다. 1. Vestigium 구현 문제이다. 2. Nesting Depth 구현 문제까지는 아니지만 거의 시키는대로 괄호를 열고 닫고 하면 끝난다. $O(n)$ 풀이. 3. Parenting Partnering Returns Worker 2명 스케줄링 문제. 그리디 문제로 유명한 well-known이다. 4. ESAb ATAd 여기서부터는 머리를 좀 썼다. 일정한 규칙으로 변화하는 길이 100의 이진문자열의 현재 상태를 맞추면 끝난다. 제한 조건은 쿼리 150번 이내이다. 쿼리란: index를 물어보면, index의 값을 알려준다. 변화의 규칙은: 쿼리 10번마다 네개의 변화 방법 중 하나가 랜덤하게 일어난다...

피곤한 날은 퍼포먼스가 확실히 떨어지는 듯 하다. 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$..

또 밀린 후기. 이번에는 퍼플 복귀전이다. And today I can't be bothered to switch between Korean and English all the time, so I'll just go with English. I mean, this blog is for me to read anyway... right? A: Kuroni and the Gifts Again I was braced to clear A as fast as possible. Read through the description in a breeze; skipped the examples. Sort the two arrays and print them out. AC at 2 minutes B: Kuroni and S..

코포에서의 첫 Div. 1 대회이다. 예상대로 개망했다. A: Journey Planning Integer array가 들어온다. Subsequence 하나를 택해 그 sum을 최대화 해야 하는데, subsequence에서 성립해야 하는 규칙이 한 가지 있다: subsequence에서 adjacent한 두 값은 두 값 사이의 value 차이와 index 차이가 같아야 한다. 잠시 생각해서 알 수 있는 사실은 A, B가 동시에 선택 가능하고 A, C가 동시에 선택 가능하다면 A, B, C가 모두 동시에 선택 가능하다는 사실이다. 따라서 선택되는 첫 element만 정한다면 그 이후에 있는 element 중 선택 가능한 모든 element를 만나는 대로 전부 다 greedy하게 주워담으면 된다... 그래서 ..