Syphon의 자기개발 일지

또 떨어진다... 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 이진탐색 기본..

자다 일어나자마자 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한 것 같았다. 빈도가 제일 높은 숫자를 최대한 떨어뜨려 배치한다면, 나머지 숫자들은 적당히 배치하여 동일 숫자간의 최소 거리를 유지할 수 있을 것 같다는 강한 직관을 느꼈다. 강한 직관은 보통 맞다. 문제가 되는 부분은, 빈도가 제일 높은 숫자가 여러..