Syphon의 자기개발 일지

요즘 대회를 하도 많이해서 슬슬 후기 남기기가 귀찮아지고 있다. 그래도 기록은 소중하니 소홀히 하지 않겠다. A: New Year Garland 한번 엄청 빨리 문제를 풀어보고 싶다는 욕심이 들어 테케 수 입력 등의 코드를 미리 작성해놓고 문제만 빠르게 읽었다. R, G, B의 개수가 정해졌을 때, 같은 알파벳이 연속으로 나오지 않도록 일렬로 배열하는 것이 가능한지 판별하면 된다. 가장 숫자가 많은 알파벳을 떨어뜨리기 위해 나머지 두 알파벳 개수의 합이 충분한지만 보면 된다(i.e. more or equal to one less than the most frequent). 2분에 AC B: Verse For Santa 정해진 시간 내에 릴레이식으로 최대한 많은 숫자의 노래를 불러야 한다. 총 제한 시간과..

🎄대회로 맞이하는 크리스마스.🎄 새해에도 코딩과 함께~ 🔥🔥🔥 A: Temporarily unavailable 실직선 위의 위치 \(a\)에서 \(b\)까지 일정한 속도로 이동할 때, 위치 \(c\)의 기지국으로부터 거리 \(r\) 초과로 떨어져 있는 시간을 구하는 문제이다. 두 구간의 교집합의 크기를 구하면 바로 해결 가능하다. 5분에 AC B1: K for the Price of One (Easy Version) 문제의 제목과도 같이 \(k\)개의 물건을 동시에 구매할 수 있다. 이때의 구매가는 \(k\)개의 물건 중 최고 가격의 물건이다. 혹은 하나의 물건을 낱개로 구매할 수도 있다. 보유한 돈의 액수가 주어지고 각 물건의 가격이 정해졌을 때, 최대 몇개의 물건을 구매할 수 있는지 구해야 한다. B..

오늘 대회는 좀 반성해야한다. C에서 한시간 반을 헤맸다. A: Shuffle Hashing 주어진 문자열을 shuffle한 후 앞뒤로 임의의 문자열을 concatenate한다. 이렇게 생성된 hash와 기존의 문자열이 주어졌을 때, hash가 valid한지, 즉 주어진 문자열로 주어진 hash가 만들어질 수 있는지를 판별하면 된다. 문자열의 길이가 100 이내로 매우 작은 편이라 naive하게 짠 \(O(n^3)\) 솔루션을 제출했지만, TLE를 받았다. 역시 기대를 저버리지 않는 Python. 그래서 알파벳 빈도의 누적 카운트 배열을 만들어 구간의 알파벳 빈도를 빠르게 계산할 수 있도록 바꾸었다. \(O(n^2)\)으로 복잡도를 낮춰 통과했다. 5분에 TLE, 13분에 AC B: A and B 두 정..

시험기간과 대회가 겹쳐 후기 작성이 다소 늦어지게 되었다. 시험 대비와 대회 참여 사이에서 조금은 고민했으나, 대회 시작 5분 전에 급하게 데스크탑을 켜고 레지스터를 마쳤다. A: Happy Birthday, Polycarp! 주어진 수 \(n\)보다 같거나 작은 자연수 중에서, 숫자 하나의 반복으로 이루어진 수의 개수를 출력하는 문제이다. 빠르게 구현하기 위해, 입력 \(n\)이 들어오면 \(n\)보다 자릿수가 같거나 작은 모든 '동일 숫자 반복으로 이루어진 수'를 \(n\)과 크기 비교하였다. 시간복잡도는 \(O(\log n)\)이다. 4분에 AC B: Make Them Odd 자연수의 배열이 들어올 때, 모두 홀수로 만들고자 한다. 홀수로 만들기 위한 연산은 특정 숫자를 골라 모든 occurrenc..

오늘도 평화롭고 쉬운 AtCoder 대회. A: November 30 두 숫자가 같은지 물어본다. Are you for real?? 1분에 AC B: Tax Rate 나누기 문제. 하지만 round down을 round로 잘못 읽어 WA를 두 번이나 추가. 2 WA 후 9분에 AC C: 100 to 105 C에 와서야 조금 생각해야 하는 문제가 나왔다. 주어진 6개의 숫자의 합으로 입력된 수 \(n\)을 만들 수 있는지 묻는 문제다. 숫자들이 전부 다 100 부근에서 놀고 있으므로, 입력된 수 \(n\) 또한 100이 들어가는 개수 기준으로 생각해 보아야겠다는 느낌이 들었다. 잘 생각해보면 어렵지 않게 100이 들어가는 개수에 따라 가능해지는 나머지 두 자리 수의 범위가 결정됨을 알 수 있다. 13분에 ..

이런 저런 일정으로 대회 참여를 못하다가, 오랜만에 복귀하게 되었다. 컨디션이 좋지 않아 평소보다는 못한 것 같지만, 레이팅 방어는 성공하였다. A: Sweet Problem 이번 대회에서 체감상 제일 어려웠던 문제다. 문제 description은 매우 간단한데, 최적의 solution을 찾는 방법을 떠올리지 못해 한참을 헤맸다. 결국 직관적으로 풀었는데, 방법이 맞았던 모양이다. 23분에 AC B: PIN Codes 최대 10개의 PIN code들을 서로 다른 code로 만들기 위한 최소 수정 횟수와 그 수정 결과를 출력하는 문제였다. 거의 문제를 보자마자 마지막 자릿수만 처리한다면 풀 수 있음을 알 수 있었다. 구현하는 것에 시간이 조금 소요되었다. 49분에 AC C: Everyone is a Win..

AtCoder 대회를 뛰고 거의 연속으로 코포 대회를 진행했다. A: Single Push 간단한 문제이지만, 불일치하는 지점의 개수가 1인 경우에 대한 예외처리를 적절히 하지 않아 이를 급하게 수정하느라 조금의 지체가 있었다. 7분에 AC B: Silly Mistake 조건에 맞도록 주어진 배열을 분할할 수 있는지를 묻는 문제이다. 같은 사원이 같은 날에 두 번 enter할 수 없다는 조건을 놓치고 그냥 전체를 무조건 하루로 잡고 전체 배열이 조건에 맞는지 확인하는 코드를 짰다. 제출하고 WA. 다시 보고 문제점을 확인, 같은 사원이 다시 enter 하려고 하는 순간 새로운 날이 시작되도록 수정하였다. Pretests passed. 하지만 동일 사원이 다시 들어오려 할 때가 아니라, 모든 사원이 다 나..

오랜만에 한 내 두번째 AtCoder 대회. A: Circle 너무 쉬워서 당황했다. 입력값의 제곱을 출력하면 끝. 1분에 AC B: Echo 얘도 쉽다. 설명 생략. 3분에 AC C: Average Length 여기까지는 보자마자 풀이가 떠오르는 문제. 평면 위 N개의 점을 순회할 때의 평균 거리를 구하는 문제이다. 모든 두 점 사이의 거리를 전부 구한 후, 이를 다 더한 후 적당한 수로 나눠서 풀었다. 9분에 AC D: Knight 이 문제는 살짝 고민했다. Knight의 두가지 움직임의 횟수가 유일하게 정해지는 사실을 깨닫기까지 시간이 좀 걸렸다. 이를 확인한 후에는 빠르게 연립 1차방정식의 해를 찾는 코드를 짰고, \( \binom nr\mod p\)의 값을 구하는 함수를 만들었다. 하지만 WA를..

요즘 우리 과의 웹/앱개발 동아리인 WaffleStudio 친구 셋과 함께 진행 중인 프로젝트는 카드 게임 '마이티'를 멀티플레이어로 할 수 있는 플랫폼, Mighty Online의 개발이다. 마이티라는 게임은 일반인들에게는 잘 알려져 있지 않지만, 일부 고등학교 학생들과 서울대를 포함한 몇몇 대학의 특정 과에서는 즐겨 플레이하는 사람들이 매우 많은, 소수에게 꾸준한 사랑을 받는 게임이다. 사실 이번 프로젝트는 '연습용'으로 내가 제안한 프로젝트이다. 팀의 멤버 네명은 각각 다른 수준의 개발 경험이 있지만, 모두 다 웹과 앱 개발 경험이 적다. WaffleStudio에 들어온 만큼, 무엇인가를 만들면서 웹/앱을 배우고 싶었고, 고민 끝에 해보기로 결정된 프로젝트가 Mighty Online인 것이다. 연습..

일주일만에 Codeforces에서 대회를 뛰었다. 대회 직전에 잠깐 잠을 자다가 못 일어날뻔 했다. 시작 10분 전에 일어나서 데스크탑을 켜고 대회 start. A: Two Rival Students 1분 이내로 풀었어야 하는 쉬운 문제. 라이벌 두명을 이웃한 학생과 x번 swap해서 최대한 멀리 떨어뜨리는 문제이다. 그냥 거리를 x만큼 더 벌리면 된다. 하지만 문제를 잘못 읽어 이웃한 학생만 swap할 수 있다는 조건을 놓쳤다. WA 추가 && 6분 낭비 후 AC B: Magic Stick 주어진 두 operation의 특성을 보고, 일정 숫자 이상이면 모든 숫자를 만들 수 있음을 알아차리면 된다. 3 이하의 숫자로 시작할 때만 잘 처리하면 되는데, 경우를 예쁘게 나누지 못해 if else 코딩하느라 ..