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 풀고 나서 보면 꽤 쉬운 문제인데, 이런 생각을 해본 적이 없어서 뇌정지가 잠깐 왔었다. 직접 이진탐색을 해보며, 찾고자 하는 값보다 왼쪽과 오른쪽에서 확인하게 되는 원소의 수를 기록하면 된다. 왼쪽과 오른쪽에서 확인하는 원소의 수가 정해지면, 경우의..

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

졸리지만 대회 시작. A: Common Subsequence 생략. 4분에 AC B: Sequential Nim 새로운 pile에서 take하는 사람이 주도권이 있다. 현재 pile에서 하나만 남기고 모든 stone을 가져감으로써 다음 pile을 다시 자기 차례에 가져갈 수도 있고, 현재 pile을 전부 다 가져감으로써 상대방한테 다음 pile을 넘길 수도 있다. 단, pile에는 두개 이상의 stone이 있어야 한다. 하나의 stone만 있는 pile의 경우, 무조건 그 하나의 stone을 가져가야 하며 차례는 상대에게 넘어간다. 시작 이후 크기 1짜리 pile이 몇개 연속되어 나타나는지를 살펴 그 홀짝성을 바탕으로 판별하면 된다. 단, 오직 크기 1짜리 pile만 있다면 승패 조건이 반대로 뒤집힌다...

지난 대회가 끝나자마자 레지스터했던 대회이다. 그때 레지스터해두지 않았다면 귀찮아서 하지 않았을 것 같다. A: Sign Flipping 문제 착각해서 뻘짓하다가 정신 차리고 홀짝성에 맞춰서 부호 부여. 5분에 AC B: Neighbor Grid 그냥 꽉꽉 채워주면 된다. 네 귀퉁이는 2, 네 모서리는 3, 나머지 값들은 4로 만들어 줄 수 있는지만 확인하면 된다. 근데 이 간단한걸 잘못 짜서 디버깅하면서 시간 다 버렸다. 4 WA 후 26분에 AC C: Element Extermination 지난 대회의 문제가 떠오르면서 이 문제 또한 greedy일 것이라는 느낌을 받았다. 삽질을 엄청 했다. 처음에는, 자료를 deque에 넣어 양 끝에서 greedy하게 두개씩 pop하고, 왼쪽 끝에서는 둘 중에 작은..