leo020630의 블로그

종강을 했다. 시험기간에는 문제가 그렇게 풀고 싶었는데, 종강하자마자 의욕이 확 식길래 랜덤 디펜스를 시작하기로 했다. 범위는 G2~D4이며, 하루에 5문제씩 뽑아서 진행할 예정이다. https://www.acmicpc.net/group/14908에서 진행 중이니 제가 뭘 푸는지 구경하고 싶거나 같이 문제를 풀고 싶으신 분들은 언제든 환영입니다ㅎㅎ 오늘은 첫날이라 시간을 기록하지 않았는데, 다음부터는 시간도 잴 예정이다. 15678 - 연세워터파크 웰노운이라 짜서 맞았다. 최근 \(k\)개 항의 최대 또는 최소를 관리해야 하는 DP는 세그 또는 PQ 또는 덱을 사용해서 해결할 수 있음이 널리 알려져 있다. 2136 - 개미 이것도 웰노운이라 신나게 짜긴 했는데, 생각해보니 번호를 구하는 방법을 몰라서 시..

slah007 선배의 추천으로 풀게 된 문제이다. 푼지는 좀 됐는데, 시험기간 탓에 이제야 포스팅한다. 문제 요약 구간 \([L, R]\) 로 나타내어지는 선분 \(N\)개가 주어진다. 만약 두 선분이 겹칠 경우, 두 선분 사이의 거리를 1로 정의한다. \(A\)번 선분과 \(B\)번 선분의 거리를 구하는 쿼리를 \(Q\)번 처리하라. 풀이 일반성을 잃지 않고 두 선분이 겹치지 않으며 A가 B보다 앞에 있다고 가정하자. 당연하게도, B에 도달하기 위해서는 매 이동마다 가장 끝 좌표가 큰 선분으로 이동하는 것이 최적이다. 이렇게 같은 행동을 반복하는 문제는 DP, 그 중에서도 Sparse Table을 사용하면 해결할 수 있다. 다만, Sparse Table을 만들기 위해서 몇 가지 생각해야 할 부분이 존재..

그냥 백준을 돌아다니다 재밌어 보여서 풀게 된 문제인데, 풀고 나서 보니 다른 사람들의 풀이와 다른 것 같아 포스팅해보려고 한다. 문제 대충 저렇게 생긴 직교 다각형이 주어질 때, 햇빛에 의해 생기는 그늘의 길이를 구하는 문제이다. 풀이 코드를 까보니, 다른 분들의 풀이(이자 정해)는 전체 둘레에서 햇빛이 비치는 부분의 길이를 빼서 구하는 방식인 것 같다. 내 풀이의 발상 난이도는 저 풀이와 비슷하거나 조금 쉽고, 접근 방향이 약간 다르다. 여집합이 아니라 그림자의 길이를 직접 구해보자. 그림을 잘 보면, 이런 식으로 각 변에 의한 그림자 길이는 그 변과 같다는 사실을 직관적으로 관찰할 수 있다. 또한, 광원이 하나이기 때문에 그림자가 겹칠 가능성 또한 없음을 파악할 수 있다. 다각형을 이루는 점이 시계..

셋은 SWERC 2018을 사용하였으며, slah007 선배와 둘이서 5시간동안 진행하였다. 추가로, DGIST의 SudaL 팀과 연락이 닿아 시간을 맞춰 진행하였다. ~0:11 slah007 선배가 앞쪽, 내가 뒤쪽을 보고 시작했으나 왜인지 A가 쉽다는 것을 내가 더 먼저 알아채 짜서 맞았다. ~0:19 slah007 선배가 E를 코딩하는 사이, B와 D가 풀 만 하다는 것을 깨닫고 풀이를 구상했다. ~0:25 E AC가 뜬 직후 B 코딩을 시작해 빠르게 맞았다. Parametric Search가 가능하다는 것과 문제에서 주어진 조건을 잘 이용하면 비교적 쉬운 방법으로 문제를 해결할 수 있다. ~0:45 D 풀이 또한 나온 상태였기에 B를 맞고 바로 코딩에 들어갔다. B보다 훨씬 많은 시간을 쓴 후 A..

1000 Solve 후기글 이후 처음 적는 기념 목적 글이다. 왜 1100 Solve가 비어있는지는 기억이 잘 나지 않는다. 1000번째 문제로 실제 대회에서 봤던 17613을 풀었던 게 기억나서 이번에도 비슷하게 내가 못하는 유형 + 실제 대회에서 보았었던 23577 (2021 ICPC L번) 을 골랐다. 이 문제로 말할 것 같으면 지난 ICPC에서 나와 우리 팀을 망하게 한 무수히 많은 요인 중 하나로, 특히 내가 오래 잡고 있었기 때문에 기억에 오래 남았다. 생각해 보니 작년에 내가 나간 큰 PS 대회가 UCPC, SCPC, PPC, ICPC로 총 4가지였는데, 모두 케웍을 못해서 말리거나 말릴 뻔 했던 것 같다. UCPC에서는 J번의 마무리 처리 케웍을 1시간동안 못해서 상격을 낮출 뻔 했고, S..

6월 5일에 solved.ac 시즌이 갱신된다는 공지가 있었다. 이를 확인했을 때 내 티어가 D4였는데, 4는 예로부터 불길한 숫자였기 때문에 D3으로 올리려고 문제를 좀 풀었다. P2~D3 범위에서 골랐는데, 랜덤으로 뽑은 것도 있고 풀이를 대충 알고 있어서 짠 것도 있고 그냥 재밌어보여서 푼 것들도 있다. 일당 하나씩은 해당 범위의 문제들을 풀었기 때문에 날짜별로 정리해보려고 한다. 5/16 - 15879 Edge Coloring 5/13 팀 연습에서 Cycle Basis가 들어가는 문제를 풀었는데, 이 문제도 비슷한 원리를 이용하는 문제라는 것이 생각나서 풀었다. 풀이는 Cycle Basis를 안다면 쉽게 찾을 수 있는 것 같다. 5/17 - 1739 도로 정비하기 랜덤으로 걸린 문제이다. 각 도로..

셋은 https://www.acmicpc.net/category/detail/1976를 사용하였으며, 4시간 동안 진행하였다. 내가 A~D, slah007 선배가 E~I, qjatn0120 선배가 J~M을 잡고 시작했다. ~0:17 브~실 총 4문제를 1트만에 모두 밀었다. ~0:22 B는 깡수학이길래 넘겼고, C를 봤는데 Simple DP로 되길래 짜서 AC. ~0:57 B를 우리 중 이런 문제에 가장 강한 slah007 선배에게 넘기고 나는 D를 봤는데, D도 못 풀겠어서 선배들이 보던 문제중 F를 잡았다. F는 보자마자 그냥 XOR 세그+스위핑이란걸 깨달았다. 좌표 압축+누적합 등 처리해야 하는 부분이 꽤 있어 코딩 컴퓨터에서 나와있는 동안 구현을 대충 해놓았고, B AC가 뜨자마자 컴퓨터에 들어갔..

qjatn0120, slah007 선배와 대면으로 하는 첫 팀연습이다. 셋은 UKIEPC 2020을 사용하였으며, 4시간 동안 진행하였다. 내가 A~D, qjatn0120 선배가 E~I, slah007 선배가 J~M을 보기로 했다. ~00:13 qjatn0120 선배가 E가 쉽다고 하셔서 컴퓨터를 넘겼는데, 틀리길래 B3 난이도인 D를 짜서 맞았다. ~00:26 이후 D와 똑같은 과정으로 slah007 선배가 J를 맞아오셨고, 나는 E AC 코드가 나오는 동안 C 풀이를 구상하고 있었다. 잘 가다가 59%에서 틀리길래 코너 케이스가 있을 것이라 생각했고, 모두 0인 경우를 예외처리 해주었더니 맞았다. ~00:45 선배들이 H, I, M을 맞아왔다. 이 문제들은 내용을 아직 몰라서 할 말이 없다. 나는 이..

ABC와 코포 Div. 1이 있어서 둘다 쳤다. AtCoder Beginner Contest 250 A. Adjacent Squares (0:01, +) *25 if문을 4개 써주면 된다. B. Enlarged Checker Board (0:04, +) *109 그냥 별 찍기다. C. Adjacent Swaps (0:07, +) *517 값을 담은 배열과 역추적 배열을 만들어서 잘 바꿔주면 된다. D. 250-like number (0:16, +) *797 우선 에라토스테네스의 체로 \(10^6\) 이하의 소수를 모두 구해준 후, 각 소수에 대해 이분탐색으로 만족하는 더 작은 소수의 개수를 구해주면 된다. E. Prefix Equality (0:23, +) *1421 \(C_i\)를 \(A_i\)가 \(..

카테고리 제목이 '오늘의 PS'인데 제목에는 당당히 7일치를 박아놓았다. 하지만 저 기간 중 문제를 풀었다고 할 날은 5월 1일과 7일 이틀뿐이었기 때문에, 한 글에 정리해보려 한다. 5월 1일 - 2022 DGIST 현풍전산배 알고리즘 대회 Open Contest 타임라인은 정확히 기억이 나지 않아 문제별 후기만 간단히 정리하도록 하겠다. A. 에어컨 전형적인 구현 문제이다. A번 치고는 까다로운 구석이 여럿 있었던 것 같다. 출력 형식 때문에 printf를 오랜만에 사용해 볼 수 있었다. B. 비즈마켓 코포 Div.2에서 볼 수 있을 것 같이 생겼다. 두 배열을 하나는 오름차순, 하나는 내림차순으로 정렬한 뒤 잘 구해주면 됐던 것 같다. C. D. 사각형 게임 (Small, Large) 오픈콘이라 두..