Syphon의 자기개발 일지

휴가 중 두번째 대회. A: Perfect Permutation Shift one. AC: 2 분 B: Party 경우를 나누어 생각하면 어렵지 않다. 일단 모든 사람을 최대한 포함시키는 것에서 시작한다. Pair의 개수가 홀수라면, 그래프에서 몇몇 정점을 제거해야한다. 제거해야 하는 정점의 집합 속에 홀수명의 친구를 가진 정점이 있다면, 그 정점만 제거해도 됨을 알 수 있다. 제거해야 하는 정점의 집합 속에 홀수명의 친구를 가진 정점이 없다면, 그 중 두 정점이 서로 친구여야만 함을 알 수 있고, 서로 친구인 두 정점만 제거해도 됨을 알 수 있다. 따라서 홀수 친구를 가진 모든 정점을 먼저 살피고, 서로 친구인 짝수 친구를 가진 정점들을 다 살피면 된다. 모두 살펴도 시간은 충분하다. AC: 20 분 ..

찍턴 휴가를 나와서 오랜만에 친 대회. 정말 오랜만에 핸디캡 없는 대회이다. (작년 말의 대회는 부상으로 인해 왼손 하나로 쳤었고, 올해 초의 대회는 군대에서 격리중에 휴대폰으로만 쳤었다. 휴대폰 대회는 후기를 남기지 못하였다.) A: Three Doors Trivial. AC: 4 분 B: Also Try Minecraft 양방향으로 낙폭 누적합을 전처리해두면 된다. AC: 12 분 C: Recover an RBS 복잡하게 생각을 하다가 꼬였다. Unique한지 아닌지만 판별하면 되므로, greedy한 접근이 가능하다. ?에 치환할 필요한 (와 )의 개수를 계산한 후, 모든 (를 왼쪽으로 몰고 )를 오른쪽으로 몰아 넣는 생각을 해보자. Invalid한 braces가 발생하는 것은 아직 열지 않은 괄호를..

손이 다쳐서 갑자기 사회...가 아니라 병원으로 튕겨나왔다. 한손으로 레이팅 방어가 될지 의문이었지만, 뭐든 해봐야 아는 법! 코포는 못참거든 ㅋㅋㅋㅋㅋㅋ A: Luntik and Concerts $a, b, c$ 각각의 홀짝성을 기준으로 8 경우로 나눠 풀었다. 알고보니 총합의 홀짝성만 따져도 됐다. AC: 10 분 B: Luntik and Subsequences Trivial. AC: 13 분 C: Grandma Capa Knits a Scarf 모든 알파벳 $k$마다 시도해보면 된다. 특정 알파벳으로 palindrome이 가능하다면, 그 알파벳을 전부 다 걷어내도 가능하다. 이 사실로 가능성 판정을 한다. $k$ 제외 다른 알파벳들로 문자열을 쪼갰을 때, 각 구역의 $k$ 개수를 대칭적으로 만들어주..

코드포스를 시작한 2019년부터 항상 언젠가 만들어야지... 하면서 미뤄오던 것이 있었다. 바로 코드포스 대회의 예제 입출력 테스트를 자동화해주는 도구이다. 대회 도중, 코드 로직을 수정할 때마다 코드포스 사이트의 입력을 복붙하는 과정이 꽤나 번거로웠고, 웹 크롤링을 통해 이 과정을 자동화해줄 수 있는 도구가 있다면 편리하겠다는 생각을 여러 번 했었다. 더불어 이 블로그에 대회 후기들을 꾸준히 남기면서, 후기 템플릿을 자동 생성해줄 스크립트 또한 있으면 좋겠다는 생각을 하게 되었다. 후기에는 각 대회 문항의 이름과 링크가 들어가야 하는데, 이를 일일이 복붙해서 링크 걸어주기가 꽤 귀찮기 때문이다. 얼마 전, 대회 후기를 작성하려던 내가 갑자기 위의 필요한 기능들을 구현해버렸다: https://github..

저녁 6시의 대회다. 이른 시간에 대회를 치게 되니 느낌이 색다르다. 정신이 더 맑은 것 같기도? A: Three swimmers Trivial. AC: 3분 B: Card Deck 어렵지 않게 최대한 큰 lexicographic 값을 만드는 문제임을 알 수 있다. 따라서 간단한 greedy 문제가 된다. 덱에서 제일 큰 숫자 기준으로 옮기기를 반복하면 된다. AC: 9분 C: Maximum width 이런 형식의 문제에 약한 듯 하다. 앞으로 최대한 붙여서 완성할 때 필요한 길이 배열과, 뒤로 최대한 붙여서 완성할 때 필요한 길이 배열을 각각 계산해 둔다면, 각 위치의 간격을 최대화했을 때의 간격을 $O(1)$ 복잡도로 구할 수 있다. 앞으로 붙인 글자 $i$개, 뒤로 붙인 글자 $n - i$개일 때 ..

자다 깨서 정신없이 시작한 대회. A: Shifting Stacks 블록은 오른쪽으로만 이동 가능하므로, 첫번째 stack부터 $i$번째까지 스택까지의 구간에 블록이 충분한지를 모든 $i$에 대해 확인해주면 된다. AC: 5분 B: Eastern Exhibition 택시거리 총합을 최소화시키는 문제인데, 택시거리 특성상 $x$축 방향 거리와 $y$축 방향 거리가 서로 독립적임을 알아차린다면 금방 끝나는 문제이다. 각 축에 대해서 값을 정렬한 후, 중앙값 하나 혹은 중앙값 두개 사이가 모두 최솟값이 된다. 하지만 나는 각 축의 거리가 독립적이라는 사실을 정말 정말 늦게 파악했고, 대회 마감 직전에 풀이를 코딩했다. 심지어 풀이도 앞서 서술한 정해와는 조금 다른데, 우연히 같은 결과가 나와서 맞았다. 대회 ..

대회가 언제였더라? ㅋㅋㅋㅋㅋㅋ 2 주 미루다 이제서야 후기를 쓴다. 이번 후기부터는 자동 생성된 템플릿을 쓴다! 대회 링크를 입력해주면 문항들을 알아서 크롤링해와서 아래와 같이 각 문항 이름과 링크가 자동으로 걸리도록 코딩하였다. 매번 문제 이름들을 복붙하고 링크를 걸어주는 것이 귀찮아서 후기를 미루게 됐었는데, 이제는 정말 간편하게 후기를 쓸 수 있게 되었다. A: Space Navigation 정말 간단한 문제임에도 불구하고 생각을 여러 차례 잘못하는 바람에 많은 지체가 있었다. AC: 10분 B: New Colony 잠시 살펴보면 그냥 구현 문제임을 확인할 수 있다. $k$ 값이 매우 큰 경우는 직접 확인할 필요가 없기 때문이다. AC: 20분 구현이 꼬여서 세번이나 틀렸다. C: Fence Pa..

간만에 망치지 않은 대회다. A: K-divisible Sum 어렵지 않다. AC: 4분 B: Inflation Greedy이다. AC: 14분 C: Longest Simple Cycle 얘도 어렵지 않다. $O(n)$으로 greedy하게 cycle들을 찾아주면 된다. 전 단계에서 만들어둔 cycle에 이어서 연장하는지, 아니면 새로운 cycle을 현재 위치에서부터 시작할 지 greedy하게 결정해주면 된다. AC: 30분 예외처리를 제대로 못해서 WA를 한번 받았다. D: Journey 시작 위치에서 RLRLRL 처럼 번갈아 길이 깔려 있는 위치까지만 도달 가능하다. RLRL / LRLR에서처럼 같은 방향이 연속해서 나타나는 지점들의 위치를 배열에 저장해두고, 각 시작 위치에 대해 좌우로 이진 탐색을 ..

빨리 풀어야 하는 대회에서는 항상 한 문제에서 막혀버린다. A: Nezzar and Colorful Balls 제일 많이 중복되는 경우만 확인하면 된다. AC: 1분 B: Nezzar and Lucky Number 럭키넘버 $d$에 대해, $a$가 $11d$ 이상이기만 하면 무조건 문제의 조건대로 표현할 수 있다. 1의 자릿수가 $d$인 숫자 하나, 10의 자릿수가 $d$인 숫자 하나로 분해하면 무조건 가능해지기 때문이다. $11d$ 이하일 경우, $d$를 몇번 뺄 수 없기 때문에 그냥 다 해보도록 구현했다. AC: 45분 놀랍게도 이게 44분이 걸렸다. C: Nezzar and Symmetric Array $d$를 정렬한 후 생각하면 된다. 배열 $a$의 값들을 수직선 위에 표시했을 때, 각 구간 값들..

오르긴 하지만 살짝 아쉬운 대회이다. A: Puzzle From the Future 요즘 코포가 어렵다. 내가 알던 A가 아니다 ㅋㅋㅋㅋㅋ 자릿수가 줄어들면 안되고, 높은 자리수가 큰 숫자가 장땡이니 greedy하게 짜면 된다. AC: 5분 B: Different Divisors 문제가 신박해서 잠시 어... 이건 뭘까... 하고 있다가 바로 직관적인 greedy 풀이가 떠올랐다. $pq$ 형태로 소수 두개가 곱해진 형태의 수를 찾는데, $p$는 $1 + d$ 이상인 숫자부터, $q$는 $p + d$ 이상인 숫자부터 찾으면 된다. 엄밀한 증명은 사실 안해봤다. (대회에서는 직관이 최고다) AC: 12분 C: Array Destruction 구현에서 자꾸 꼬여서 풀기까지 오래걸린... 것도 맞지만, 구현 ..