Syphon의 자기개발 일지

개강 이후 정말 바쁘게 살다가 정말 오랜만에 코포를 뛰었다. 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하게 주워담으면 된다... 그래서 ..

몰아쓰는 후기 #3 이번 주는 대회가 많다. A: Three Strings 빨리 Div. 1에 안착해서 이런 문제 후기들 생략하고 앉아있지 않아도 되면 좋겠다. 3분에 AC B: Motarack's Birthday 몇몇 칸이 비어있는 정수 배열이 입력으로 들어온다. 그 비어있는 칸들은 일관되게 $k$로 채울 것이다. 인접한 값들 사이의 차의 최댓값을 $m$이라고 할 때, $m$을 최소화하는 $k$값을 구해 $m$과 $k$ 모두 출력해야 한다. 다들 이진탐색으로 많이 푼 것 같고 problem tag에도 binary search가 있지만 나는 이 문제를 왜 그렇게 푸는지도 모르겠고 어떻게 그렇게 푸는지도 모르겠다. 그냥 빈 칸과 인접한 수들 중 제일 큰 값과 제일 작은 값 중간의 값을 $k$로 택하면 된다..

몰아쓰는 후기 #2 A: Erasing Zeroes 이진 문자열. 1 사이에 낀 0들의 개수를 출력하면 된다. 2분에 AC B: National Project $n$칸짜리 highway 수리를 해야 하는데, 하루에 $1$칸 이하만 수리할 수 있다. 수리를 시작하는 날부터 좋은 날 $g$일과 나쁜 날 $b$일의 주기가 반복된다. 좋은 날에 수리한 highway의 비율이 절반 이상이기 위해서 필요한 최소 날의 수는? 그냥 대놓고 이진탐색이다. 1 WA 후 15분에 AC 이진탐색의 범위를 잘못 잡아서 WA를 한번 띄웠다. C: Perfect Keyboard 26개 알파벳을 일렬로 배열해 키보드를 만들어야 하는데, 입력으로 들어오는 문자열에서 인접한 알파벳은 키보드에서도 인접해야 한다. 일렬로 배열할 경우 한 ..