Syphon의 자기개발 일지

몰아쓰는 후기 #1 A: Non-zero 정수의 배열이 있다. 배열의 한 원소에 1을 더하는 것을 하나의 operation으로 정의할 때, 배열의 sum과 product가 모두 0이 아니기 위해서 필요한 operation의 최소 횟수를 구해야 한다. Product가 0이 되지 않기 위해서는 배열 내의 0들을 우선 치워야 한다. 1씩 더해서 치운 후에 배열의 sum이 0이 아니라면, 아무 곳에서 1을 얹어주면 될 일이다. 5분에 AC B: Assigning to Classes 주어진 숫자들을 두 그룹으로 나누어 각 그룹의 median의 차이를 최소화해야 한다. 모든 숫자들을 정렬해 나열해놓고, 그 중에서 두번째 그룹의 median값으로 만들고자 하는 숫자를 정하고, 방금 정한 median값의 좌우로 하나씩..

오늘은 귀찮다. 사실 오늘만 귀찮은 것은 아니다. 대회를 한지도 벌써 일주일이다. 일주일동안 귀찮았고, 오늘도 귀찮다. 그래서 이번 후기는 대충 쓰려고 한다 ㅎ 문제 설명 생략한다. 문제 링크 생략한다. 대회 링크는 그래도 있어야겠지. A 그냥 홀수 digit이 두개 이상 있는지 확인하면 되는 것을 괜히 숫자들을 지워나가며 조건을 충족시키려고 하다가 4 WA에 1 RTE를 띄우고서야 뻘짓을 멈추고 풀이를 떠올렸다. 17분 AC. B 그려보고 조금 생각을 해보니 양쪽 끝에서부터 최소 1 씩 증가하면서 중간 어딘가에서 최고점을 찍어야 했다. 증가하도록 깍을 수 있는 부분과 감소하도록 깍을 수 있는 부분을 양쪽 끝에서 확인하고 두 부분이 겹치는지 확인하면 된다. 별 문제 없이 풀이를 떠올렸고, 구현까지 총 1..

맞웨틀(맞앗는대 웨 틀렷지?) A: Display The Number LCD 패널에서 흔히 볼 수 있는 7 segment display가 있다. $n$개의 segment만 활성화 시킬 수 있을 때, display 가능한 최대의 수를 출력해야 한다. 생각과정: 가성비가 최고로 좋은 9를 최대한 많이 출력해야겠다 -> 한 숫자의 가성비가 중요한 것이 아니라 자릿수가 최대한 많아야겠군 -> 1만 잔뜩 출력하다가 segment 개수가 남으면 첫 자리수를 키우자! 1 WA 후 11분에 AC A 치고는 쉽지 않은 편이었으나 11분이나 걸린 것은 unacceptable이다. B: Infinite Prefixes 주어진 이진문자열 $s$가 무한히 반복되는 문자열 $S=sssss...$와 주어진 정수 $x$가 있다. 임..

지난 대회에서 파이썬당한 이후 이번에는 C++로 C와 D를 풀려고 했으나 파이썬의 유혹을 이기지 못하고 이번에도 전부 다 파이썬으로 해결하였다. 하지만 오히려 파이썬을 씀으로써 D에서의 오버플로우 문제를 피해갈 수 있었다. A: ConneR and the A.R.C. Markland-N $0$으로 채워진 배열이 있고 배열에서의 현재 위치가 정해져 있다. 이 배열의 특정 위치들을 $1$로 바꿔놓았을 때, 현재 위치로부터 $0$이 있는 위치까지의 최단거리를 구해야 한다(사실 주어진 문제의 형식은 이와 좀 다르지만 앞의 설명과 본질적으로 같은 내용이다). 단순히 현재 위치로부터 양 옆으로 linear 하게 탐색하였다. 4분에 AC B: JOE is on TV! $n$명의 사람들을 대회에서 탈락시켜야 한다. 사..

밖에 나와있는 관계로 대회를 치지 못할 것 같았지만, 11시 6분에 대회를 뛰자는 Nyso의 연락을 받고 갑자기 필을 받아서 허겁지겁 집으로 향했다. 음주를 꽤나 한 상태였고, 집에 들어와서 컴퓨터를 켰을 때는 이미 13분가량 늦은 상태였지만 지난번에도 조금 늦어 포기한 대회가 매우 아쉬웠던 경험이 있어서 이번에는 핸디캡에도 불구하고 참여하기로 했다. A: Deadline 정수 $n$과 $d$가 정해졌을 때, 부등식 $x+\lceil \frac {d}{x+1} \rceil \leq n$를 만족하는 정수 $x$의 존재성 판별 문제이다. 부등식의 좌변을 ceiling function을 무시하고 미분해 극소가 되는 실수 $x$값을 찾은 후, 그 주변의 정수 2000개를 조사하는 방식으로 해결했다. 19분에 A..

새해의 첫 대회이다. 구사과님의 출제로 오랜만에 코포에서 한글을 본다. A: New Year and Naming 매우 한국적인 주제의 등장에 웃겼다. 연도가 주어지면 육십갑자를 출력하면 된다. 2분에 AC B: New Year and Ascent Sequence 배열 $n$개가 들어온다. 이들 중 두개를 중복을 허용하여 골라 concatenate했을때, 연속된 두 숫자 중 증가하는 숫자가 있다면 이는 ascent sequence이다. (사실 ascent sequence의 조건은 $i

Goodbye 2019. What a year it has been. 올 한해가 지나면서 내 코딩인생 5년차, CP 도전 1년차를 마무리하게 되었다. 컴퓨터공학부의 입학과 함께 CP의 세계에 입문하게 된 2019년은 나에게 조금 더 특별한 해가 되었다. Goodbye 2019, and hello 2020. What a year to come! CP와 개발 공부를 계속해나가며 더욱 발전할 다음 1년을 기대해본다. A: Card Game A에서는 본 적 없었던 긴 description에 살짝 당황했지만, 내용이 매우 straightforward해서 약간 웃겼다. 뭔가 길게 썼지만 요지는 별로 없는 느낌? 두 배열이 들어올 때, 각 배열의 최댓값의 대소를 비교해주면 된다. 3분에 AC B: Interestin..

요즘 대회를 하도 많이해서 슬슬 후기 남기기가 귀찮아지고 있다. 그래도 기록은 소중하니 소홀히 하지 않겠다. 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 두 정..