Syphon의 자기개발 일지

빨리 풀어야 하는 대회에서는 항상 한 문제에서 막혀버린다. 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 구현에서 자꾸 꼬여서 풀기까지 오래걸린... 것도 맞지만, 구현 ..

또 떨어진다... A: Replacing Elements 쉬운데 어렵게 생각하다가 3분이나 걸렸다. 지금 생각하면 1분컷 문제... 3분: AC B: String LCM 직관적으로 풀이가 떠올랐다. 두 문자열의 길이를 기준으로 lcm이 되도록 곱해준 후, 두 문자열이 일치하는지 확인하면 된다. 8분: AC C: No More Inversions 오늘 레이팅 하락의 원인. 문제를 잘못 이해해서 50분가량을 날렸고, 제대로 읽은 이후에도 풀이가 떠오르지 않아서 결국 D로 넘어갔다. D를 해결하고 돌아와서야 제대로 된 접근을 시작했지만, 남은 시간이 너무 짧아서 대회 시간 이내에 해결하지 못하였다. Constructive algorithm 문제들은 너무 운빨을 많이 타는 것 같다.. D: Program $x$..

역대급으로 당황스러웠던 대회. A: Wizard of Orz A치고 어려웠다. 문제 맘에 안든다. 8분: AC B: Hills And Valleys $O(n)$ 구현문제인데, 다른 틀린 풀이를 붙잡고 이게 왜 안되지??? 하다가 끝났다. 그런데 해결한 사람 숫자를 보면 나만 못푼 것 같지는 않다. 얘도 문제 맘에 안든다. 5 WA C: Three Bags Constructive algorithm이다. 답을 알면 간단한 문제인데, 딱히 좋은 문제로 느껴지지는 않았다. 그래서 설명도 안할거다 ㅎ (절대 귀찮아서 아님) 1시간 22분에 AC 총평 One hour into the competition인데 A밖에 못푼 상황이었어서 엄청 당황스러웠었다. 그런데 그 상황에서의 레이팅 하락이 20정도밖에 안돼서 더 당..

와 후기 엄청 밀렸다 ㅋㅋㅋㅋ A: Strange Partition 하나도 안합치기 vs 다합치기 2분에 AC B: Strange List 구현문제. 그냥 각 원소가 몇개 있는지 저장해주면서 작업을 해주면 된다. 22분에 AC 하지만 파이썬당해서 C++로 다시 짜느라 20분이나 걸렸다 ㅠㅠ C: Strange Birthday Party Greedy. 34분에 AC 하지만 오타로 인해 이게 왜 안되지?? 하면서 시간을 버렸다.. D: Strange Definition Adjacent의 정의를 잘 분석해보면, 두 숫자의 곱이 제곱수인지의 여부와 일치하는 것을 확인할 수 있다. 결국 각 숫자를 (제곱수) * (제곱수가 포함되어 있지 않은 수)로 분해시켜서 (제곱수가 포함되어 있지 않은 수)에 따라 groupi..

지난 송년대회에 이어 이번 송년대회도 망했다. Just more so this time. A: Bovine Dilemma 정말로 trivial. 3분에 AC B: Last minute enhancements Greedy. 5분에 AC C: Canine poetry C 치고 어려웠다. 모든 palindrome은 결국 substring으로 길이 2 또는 3짜리 palindrome을 갖고 있다는 생각으로 출발했다. 길이 2와 3짜리 palindrome의 생성을 방지하기 위해서는 특정 캐릭터 기준 앞과 뒤의 캐릭터 두개씩을 살펴야 한다. 고로 문제의 해결 방법은, $O(n)$으로 문자열을 통과하면서 앞뒤 두개씩의 문자를 살피며 적절한 수정을 해주는 것이다. 25분에 AC D: 13th Labour of Hera..

2개월만에 참여하는, 종강 후 첫 대회이다. A: Regular Bracket Sequence A번 문제 치고 문제가 복잡해서 시간을 많이 뺐겼다. 6분에 AC B: Red and Blue 각각의 누적합 최댓값을 더해주면 된다. 이게 왜 11분 걸렸지..? 17분에 AC C: Building a Fence 각 x축 위치마다, fence를 build할 수 있는 구역이 하나의 연속된 구간으로 정해짐이 문제 풀이의 핵심이다. $O(n)$으로 이 구역을 계산해나가면 된다. 43분에 AC D: Ceil Divisions 정말 많은 시간을 투자한 문제다. 대회 종료 후 두명의 친구에게 물어본 결과, 세명이 전부 다 다른 풀이로 해결했었다. $n$과 하나의 숫자만을 남기고 전부 다 $1$로 바꿔놓고, 두 숫자를 남은..

잠시 과제와 시험이 없는 틈을 노려 무려 두달 반만에 코드포스 대회를 접수했다. A: Reorder 문제를 해석하는 순간 사실상 끝난다. Reordering은 낚시. 2분에 AC B: Prime Square 여러 가지 풀이가 있는 듯 하다. 나같은 경우, $1$을 $n - 1$개 배열한 후, 더해서 소수가 되는 숫자 하나를 더 추가해 하나의 행을 만들었다. 이 행을 한칸씩 밀어 배치해주면 square가 완성된다. 13분에 AC C: Binary Search 풀고 나서 보면 꽤 쉬운 문제인데, 이런 생각을 해본 적이 없어서 뇌정지가 잠깐 왔었다. 직접 이진탐색을 해보며, 찾고자 하는 값보다 왼쪽과 오른쪽에서 확인하게 되는 원소의 수를 기록하면 된다. 왼쪽과 오른쪽에서 확인하는 원소의 수가 정해지면, 경우의..

대회를 너무 캐주얼하게 진행했더니 캐주얼하게 망해버렸다. 원래 같았으면 대충 윗공대에서 치렀을텐데, 두 대의 카메라를 동원해 Zoom에 접속해 컴퓨터 화면과 팀원들이 나오도록 설치해 둔 상태로 대회를 진행해야 한다는 번거로운 온라인 대회 규칙 때문에 서울대입구역의 토즈 스터디룸을 빌려 대회를 진행하게 되었다. 대회에서 시도한 문제 순서대로 정리하겠다. I: Project Teams 스코어보드를 참고해 제일 쉬운 문제인 I를 먼저 잡았다. 문제를 다 읽기도 전에 정렬 후 앞뒤로 짝지어주는 well-known 풀이가 떠올랐다. E: Cycle Game 그래프를 그려나갈 때, 사이클이 생기는 시점을 감지하면 된다. 읽자마자 UFDS를 떠올렸으나, 문제를 잘못 이해한 Nyso가 다른 방법으로 시도한 후 한번 실..

대학을 와서 치는 두번째 SNUPC다. 작년, 나의 레이팅 상승 추이를 보며, 2020년에는 SNUPC의 Division 1에 출전할 수 있으리라 생각했던 것이 기억난다. 안타깝게도 1년 사이에 큰 폭의 실력 상승은 없었고, Division 1에 출전할 용기 또한 없었다 ㅋㅋ 요즘 들어 CP에 조금 소홀해진 듯한 느낌이 드는데, 이런 와중에 치른 대화라 그런지 작년의 열심은 없었던 것 같다. 코로나의 여파로 인해 집에서 치뤄서 그런가..? 이제 시작한 2학기에는 작년처럼 조금 더 열심히 실력을 업그레이드할 수 있으면 좋겠다. 암튼 대회 스타트..! A: 수면 패턴 구현 문제다. 파이썬으로 퍼솔 달성!! B: 단어 개수 세기 역시 구현 문제다. 파이썬으로 퍼솔 달성!! C: 넴모넴모 2020 이진탐색 기본..