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..

처음 오렌지를 찍고 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 라운드를 망친 원흉입니다...

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법을 이용해 마지막에 처리해준 후 답을 구하면 깔끔하게 구..

지난 글에서 추천받은 대로 이번에는 OI Checklist에서 문제를 골라 보았다. OI Checklist에서 하나를 뽑으려니 감이 잘 안와서 POI 문제들이 많은 https://www.acmicpc.net/workbook/view/1939에 가 하나를 골라 보았다. 고른 문제는 POI 2012의 Distance이다. 문제 요약 두 자연수 \(x, y\)의 거리 \(d(x,y)\)를 \(x\)에 소수를 곱하거나, 나누는 연산을 해 \(y\)에 도달하기 위한 최소 연산 횟수로 정의하자. 배열 \(A\)가 주어질 때, 각 \(i\)에 대해서 \(d(A_i,A_j)\)가 최소가 되는 \(j\)를 구하여라. 풀이 우선, 같은 수가 여러 개 있는 경우는 전처리로 해결해 줄 수 있으므로 모든 수가 다르다고 가정하자..

어제 갑자기 블로그 조회수가 튀었길래 원인을 확인해보았더니 모 PS 커뮤니티에서 의문의 PS러가 이 블로그를 일종의 우수 블로그로 선정해주었다는 사실을 알게 되었다. 엄청난 분들과 함께 이름이 올라가 있어 기분이 좋았다. 뽑힌 김에 블로그 활동을 조금 더 성실히 해 보고자 오늘 있던 코포 후기부터 작성해보려 한다. A. Flip Flop Sum (0:02, +) 원래 합을 \(S\)라 하자. 모두 1이면 \(S-4\), 연달아 있는 -1이 하나라도 있으면 \(S+4\), 모두 아니면 \(S\)가 답이다. B. The Forbidden Permutation (0:14, +1) 문제가 좀 억지스럽다. 일단 Not good인지 판별을 먼저 하고, Not good이라면 인접한 쌍을 역전시키거나 거리를 \(d\)..

12월의 마지막 날에 쓴 화풀이 글 이후로 처음 쓰는 블로그 글이다. 1달 동안은 PS를 거의 하지 않았다. Hello BOJ 떨 때문도 있고, 연습시킨다고 모은 동아리 사람들의 참여율이 저조해 준비할 맛이 잘 안나서 그것도 던졌다. 그 결과 코포랑 앳코더도 많이 걸렀고, 백준도 그냥 브론즈로 스트릭만 채우고, 버추얼도 하기로 했었는데 상황이 잘 맞지 않아 몇 번 못했다. 그 와중에 일은 잔뜩 벌여놔서 문제를 내야할 일이 굉장히 많았다. 하루 종일 연구실에 앉아서 읽으라는 논문은 안 읽고 문제 낼 생각만 하는데, 어째 내가 생각한 문제들은 다 구데기인 것 같다.. 좋은 문제들을 좀 보면 아이디어가 떠오를 수도 있다고 생각해 어렵고 좋은 문제들을 좀 풀어 보려 한다. 주로 클래스 문제들이나 국내 최고의 인..

ICPC 준비용으로 다이아 중하위 정도의 모르는 주제들을 공부하고 있다. 그러다 학교 알고리즘 수업 과제로 이 문제가 나왔던 것이 생각나서 한 번 짜 보기로 했다. 핸드라이팅 과제였기 때문에 짜둔 코드가 없어 애먹긴 했지만, 어찌저찌 이 문제를 풀고 나서 보니 마땅한 한국어 설명 글도 없고(아마), 몇몇 팀 팀노트에 코드가 있긴 하지만 이해가 힘들고 내가 푼 방법과 다른 것 같아 설명 목적으로 글을 작성하려 한다. 문제 요약 볼록 다각형 밖의 점 \(P\)에서 다각형으로 접선을 그었을 때 생기는 두 접선의 접점을 구하여라. 편의상 볼록 다각형의 세 꼭지점이 일직선을 이루지 않고, 점들이 반시계 방향으로 정렬되어 있다고 가정하자. 만약 접점이 두 개일 경우, \(P\)와 가까운 점을 접점으로 한다. 풀이 ..