leo020630의 블로그

Div. 1을 돌자는 menborong님의 의견이 있어서 Div. 1을 돌았다. 어차피 C까지는 Div. 2에도 다 있어서 상관 없었던 것 같다. A. Array Elimination (0:03, +) \(k\)는 비트별로 봤을 때 1의 개수의 공통 약수여야 한다. gcd를 구해 주면 된다. 모두 0일때만 조심하자. B. Frog Traveler (0:52, +3) 이 테크닉을 박으면 풀리는 형태라 박았다. 루트 버전으로 짜고 MLE를 3번 받은 후에야 세그트리 모양으로 갈아타서 맞았다. 정해가 쉬운데 조금 더 생각을 하는게 옳은 방향이었던 것 같다. C. Optimal Insertion (1:48, +2) B의 원소들을 넣어야 하는 최적의 위치를 찾아주자. B의 원소를 오름차순으로 보면서, 각 위치에 ..

:god: tlsdydaud1님이 세팅하신 라운드이다. 역시 버츄얼로 돌았다. A. Distance and Axis (0:03, +) \(A\)의 위치는 \(x = 2y+k\)꼴이 되어야 한다. \(n\)이 \(k\) 미만이면 \(k\)까지 옮기고, 아니면 최대 1칸 이동해 조건을 만족시킬 수 있다. B. Ternary Sequence (0:10, +) 비용이 2-1인 경우와 1-2인 경우가 아니라면 다 0이라는 것을 알 수 있다. 따라서 2를 최대한 써주고 -2를 최소한으로 쓰면 된다. C. Mere Array (0:15, +) 최솟값을 \(m\)이라 하자. \(gcd(m,mk)=m\) 이므로 \(m\)의 배수들끼리는 위치를 자유롭게 바꿀 수 있다. 따라서 \(m\)의 배수들끼리 정렬해준 후 전체 배열..

방학 기간에 동아리 부원들과 1일 1버츄얼을 돌리기로 했다. A. Replacing Elements (0:02, +) 정렬을 한 후, \(d\)보다 큰 수는 \(a_1 + a_2\)로 바꿔주어야 한다. B. String LCM (0:06, +) 길이를 \(|s||t|\)까지만 확인해보면 된다. 그냥 짜주자. C. No More Inversions (0:30, +1) 그냥 밑바닥에서 규칙을 찾아야 하는 코포식 문제다. 뭔가 해보다 보면 대칭인 부분을 잘 뒤집어주면 된다는 사실을 알 수 있다. 자세한 증명은 에디토리얼에 있다. D. Program (0:42, +) 더하는 수가 +-1로 연속적이므로 누적합의 최댓값과 최솟값을 구하면 된다. 앞에서부터의 최대, 최솟값과 뒤에서부터의 최대, 최솟값을 저장하면 해결..

A. Game with Board (0:06, +1) $n$이 5 이상이면 Alice가 1을 두 개만 남기고 줄 수 있다. 그렇지 않은 경우에는 Bob이 항상 이긴다. 대충 생각했다 한 번 틀렸다. B. Keep it Beautiful (0:11, +) 정렬된 상태인지 검사하고, 만약 깨진다면 그 뒤가 여전히 정렬된 상태이면서 첫 번째 수보다 작은지 계속 검사해주면 된다. C. Ranom Numbers (0:32, +) C치고 굉장히 어려웠다. 뭔가 그리디적인 방법을 시도해보고 싶지만, 그러다간 말리기 쉽다. 숫자 종류가 5개로 작으므로 모든 경우를 다 시도해보자. 우선 주어진 문자열에 대한 답을 계산한 후, 문자를 하나씩 바꿔볼 것이다. 문자를 바꾸면 이전에 위치한 문자들의 부호가 달라질 수 있는데, ..

2000번째 문제로 골라 풀게 되었다. 사실 원래 고른 문제는 https://www.acmicpc.net/problem/25950 이거였는데, 논문을 읽다 보니 며칠 안에 될 것 같지가 않아 그냥 북마크에 있던 적절히 재밌는 문제를 하나 골랐다. 점이 2개인 경우를 생각해보자. 점 \((a,b)\)와 \((c,d)\)가 있고, \(a < 0 < c\)라 하자. 이러면, \((a,b)\)와 \((-c,d)\)를 잇는 직선을 선대칭한 두 직선 위에 점을 각각 올려놓는 것이 최적이라는 사실을 알 수 있다. 이 경우 두 점의 이동거리의 합은 \(\sqrt{(a+c)^2+(b-d)^2}\)이다. 만약 \(a\)와 \(c\)의 부호가 같다면 어떻게 될까? 두 점의 이동거리의 합은 \(\sqrt{(a+c)^2+(b-..

P4부터 시작했다. 18138. 리유나는 세일러복을 좋아해 (P4, 17:58) 이분 매칭 기본 문제이다. 코드를 안 보고 짠 데다가, 짧은 DFS 코드가 기억이 나지 않아 에드먼드 카프를 짜서 시간이 좀 걸렸다. 20560. 맛집 탐방 (P3, TLE) 갓문제들의 산실인 나코더 송년 대회 문제이다. 비슷한 문제(정확히는 이 문제의 하위호환)를 얼마 전에 풀었어서 첫 번째 조건은 어렵지 않게 구할 수 있었다. SCC로 만든 DAG에서 위상 정렬의 결과가 유일하면 된다. 문제는 두 번째였는데, 대충 생각했을 때 첫 번째 조건에 더해 DAG의 모양이 체인이면 된다는 사실을 알 수 있었다. 그리고 그대로 구현했더니 무수한 WA의 늪에 빠지고 말았다. 구현량이 좀 있어서 시간이 부족하기도 했고, 원래 한 번 말..

PS를 어떻게 할까 생각하다 어디서 본 좋고 재밌는 방법이 떠올라서 도전해본다. 랜덤으로 문제를 뽑아서, \(30 + max(0, (x-G1)*5) \) 분 안에 문제를 푸는 데에 성공하면 티어를 하나 올리고, 풀지 못하면 내린다. 자세한 사항은 https://blog.naver.com/bnb2011/222621250928 를 참고하시면 된다. 손도 풀 겸 G5부터 시작했다. 2187. 점 고르기 (G5, 11:56) G5인데 풀이가 바로 떠오르지 않아 당황했다. 한 5분정도 문제를 천천히 살펴보니 직사각형의 크기가 주어진다는 것을 알 수 있었다. 왼쪽 변의 좌표를 고정하고, 해당 x좌표에 들어오는 점들을 모은 후 스위핑해주면 된다. 이건 약간 멍청한 풀이고, 똑똑한 다른 풀이도 꽤 있는 듯 하다. 21..

말도 안 되게 길었던 3학년 1학기가 드디어 끝이 났다. 지난 4달간 블로그에 쓴 글은 단 4개이다. 대회 운영 후기 글이 3개, IM 찍고 신나서 쓴 글이 하나인 것을 생각하면 써야할 글들만 쓰고 만 셈이다. 블로그 포스팅을 소홀히 한 점을 속죄할 겸, 지난 학기에 대한 회고를 간단히 해 보려 한다. 우선 어떻게 지냈는지 간단히 소개한 후, 얻은 것과 잃은 것, 그리고 느낀 점에 대해 설명하도록 하겠다. 무엇을 했는가? 우선 본인의 이번 학기 시간표를 먼저 볼 필요가 있다. 위 시간표는 20학점짜리이다. 20학점은 사실 많긴 하지만, 죽을듯이 많냐 하면 그건 또 아니다. 하지만 저 시간표의 무서운 면은 20학점이 20학점이 아니라는 데에 있다. 과목 별로 무엇을 하는 과목인지 하나씩 간단히 살펴보도록 ..

굉장히 오랜만에 블로그 글을 쓴다. 이번 학기가 끝나고 따로 글을 쓰겠지만, 정말정말 바빴다. 때문에 따로 시간을 투자해서 하는 PS는 거의 하지 못했고, 코포나 앳코더 정도만 간간히 쳤다. 그마저도 시간이 없어 블로그에 따로 글을 쓰진 못했다. 그리고 이번 학기가 그렇게 바빴던 이유 중 약 반 정도는 지난 UDPC와 이 글에서 쓸 PPC가 차지한다. 왜 바빴는지 대회 준비 과정을 한번 되짚어보도록 하겠다. 대회 링크 : https://www.acmicpc.net/category/845 발단 및 출제 과정 대회가 1학기로 당겨지는 것이 확정이었기에 2월부터 준비를 시작했다. 출제진은 기존 3명에, 작년 대회 우승자인 kwoncycle과 준우승자인 (그리고 대학원생이라 출전을 하지 못하는) menboron..

그간 참여한 대회 중 가장 공을 많이 들인 제1회 UDPC가 끝이 났습니다. 사실 세부적인 부분으로 들어가면 아직 끝난 것은 아니긴 한데, 그래도 기억이 조금이나마 살아있을 때 글을 쓰려 합니다. 대회 링크 : https://www.acmicpc.net/category/detail/3563 발단 이 대회가 처음 구상된 것은 무려 1년 전 쯤입니다. 한창 PS에 뇌가 절여져 있던 저는 여느 때와 다름없이 학교에 PS를 하는 사람이 너무 없음에 대해 한탄 중이었습니다. (사실 이건 지금도 똑같습니다.) 지리적으로도, 사회적으로도 포스텍은 PS 변방에 속했기 때문에 SUAPC를 여는 신촌 연합이나, shake!를 여는 경인지역 연합처럼 같이 공부를 하거나 대회를 열 수 있는 대학이 있으면 좋겠다고 생각했습니다..