leo020630의 블로그

주말에 앳코더 2개, 코포 2개를 쳤는데 언레는 대충 치고 레이티드는 이상한 짓 해서 말았습니다. 몸 컨디션이 별로였는데 결국 퍼포에 영향을 미치네요.. 이상한 요소로 억까당하니 마음이 꺾였습니다. 다음 라운드부터 다시 열심히 정리해보도록 하겠습니다ㅜ

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

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