leo020630의 블로그

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!를 여는 경인지역 연합처럼 같이 공부를 하거나 대회를 열 수 있는 대학이 있으면 좋겠다고 생각했습니다..

처음 오렌지를 찍고 1년 2개월이 지난 후, 드디어 International Master(찐렌지)에 도달했습니다. 하지만 이 과정이 일반적이지 않고 너무나도 기묘했기 때문에 글으로 기록해보려 합니다. 찐렌지에 도달한 라운드는 한국 시간 기준 화요일 밤에 있었는데, 토~화 4일동안 친 코드포스 3개와 앳코더 2개 라운드에 대한 후기와 전체적인 소감을 다룰 예정입니다. 카테고리는 애매했는데 그냥 CP로 두기로 했습니다. 2/25 (토) 21:00 - AtCoder Regular Contest 157 A. XXYYX (0:10, +4) *348 생각을 대충 하고 넘어갔더니 A번에서 4번 틀리고 10분이 걸렸습니다. 문제 자체는 쉽습니다. B. XYYYX (1:06, +8) *1529 라운드를 망친 원흉입니다...

대회 링크: https://www.acmicpc.net/category/detail/3517 UCPC를 제외하면 Call for Task를 받는 거의 유일한 대회인 SUAPC이다. 지난 여름에 문제를 여럿 넣어서 1개만 뽑혔기에, 이번에는 2개만 제출하였다. 2개중 1개가 선정되었고, 2문제를 출제하게 되었다. 이에 대해선 후술하도록 하겠다. 어차피 여기가 아니면 못 쓸 문제들이라 부담 없이 냈는데, 어쩌다가 대회 3개를 동시에 운영해야 하는 상황이 되어 버려서 SUAPC에는 상대적으로 정성을 많이 쏟지 못했다. 다른 출제/검수진 분들께 죄송할 따름이다. 웬만하면 전 문제 검수를 하는 편인데, 이번 대회에는 검수를 못 한 문제가 생겨서 좀 슬펐다. 문제별 후기 A. 카트라이더: 드리프트 / 출제자 : a..

A. Two Towers (0:02, +) B를 뒤집어서 합친 후 끊는 것으로 생각할 수 있다. RR이나 BB가 최대 1번 등장하면 YES, 아니면 NO이다. B. Ideal Point (0:06, +) 옆 두 점과 비교해 더 많기 위해서는 결국 [x, x] 형태가 존재하거나 [~,x], [x,~]가 하나씩 존재해야 한다. 이를 체크해주면 된다. A와 B 모두 \(O(N)\)에 풀 수 있으나 발상이 어려워서인지 제한이 작았다. C. Tea Testing (0:13, +) B에 대한 누적합 배열을 만들고, 각 차에 대해 이분탐색을 해주면 각 차를 온전히 먹는 사람과 일부만 먹는 사람을 구할 수 있다. 온전히 먹는 사람은 구간으로 나타나는데, imos법을 이용해 마지막에 처리해준 후 답을 구하면 깔끔하게 구..