leo020630의 블로그

3일차 랜덤 디펜스이다. 범위는 P4~D5이다. 14286 - 간선 끊어가기 2 1824 - 도미노 1310 - 달리기 코스 각 문제의 지문을 읽고 그에 맞는 알고리즘을 코딩해주면 된다. 2244 - 민코프스키 합 정의에 의해 생기는 \(NM\)개의 점으로 컨벡스 헐을 구해주면 된다. 14179 - 크리스마스 이브 할 게 많아서 풀지 못했다. 업솔빙 예정 셋이 지나치게 알고리즘 연습문제들만 나와서 그닥 재미있지는 않았다. 내일은 조별과제를 해야 해서 아마 14179의 업솔빙을 빼면 랜덤 디펜스는 진행하지 않을 것 같다.

2일차 랜덤 디펜스이다. 2038 - 골롱 수열 지문이 이해가 되지 않아 약간 헤멨다. 수열의 특징을 파악한 후 최댓값이 크지 않을 것이라고 추측하면 맞을 수 있다. 20930 - 우주 정거장 KOI 개구리 점프의 2차원 버전이다. 그 문제에서 하는 것을 2번 해주면 된다. 13174 - 괄호 23799 - 리브 매칭 열심히 생각하다 집중도 잘 안 되고 문제도 어려워서 포기했다. 20188 - 등산 마니아 문제에서 요구하는 것을 잘 나누어 수식으로 표현하면 DFS 한 번으로 정답을 구할 수 있다. 분명 G2~D4 범위에서 돌렸는데, 어제 오늘 10문제 중 P4~P1이 단 하나도 나오지 않아 연습이 잘 되지 않았다. 내일부터는 범위를 P4~D5로 바꿀 예정이다.

종강을 했다. 시험기간에는 문제가 그렇게 풀고 싶었는데, 종강하자마자 의욕이 확 식길래 랜덤 디펜스를 시작하기로 했다. 범위는 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을 만들기 위해서 몇 가지 생각해야 할 부분이 존재..

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

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

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) 오픈콘이라 두..

A. Subtle Substring Subtraction (00:04, +) 평소 A치고 어려웠다. 문자열의 길이가 짝수면 자명하게 선공이 다 지울 수 있고, 홀수라면 첫 글자를 남기거나 마지막 글자를 남기는 것이 최적이다. B. A Perfectly Balanced String? (00:14, +) B답게 쉬울 것 같아서 적당히 찍었더니 맞았다. 내가 한 가정은 '두 같은 알파벳 사이에 다른 모든 알파벳이 최소 하나씩은 있어야 한다' 이다. C. Palindrome Basis (00:18, +1) 팰린드롬의 수가 적당히 작기 때문에 \(O(NM)\)에 냅색을 써주면 풀 수 있다. D. Lost Arithmetic Progression (01:18, +1) 우선 예외 케이스를 잘 분석해서 0, -1에 대..

앳코더와 코드포스 글로벌 라운드가 있었다. AtCoder Beginner Contest 249 A. Jogging (0:05, +) *103 지문이 이상하게 쓰여 있어서 좀 헤멨다. 문제 자체도 평소 ABC A보다 어려웠다. B. Perfect String (0:07, +) *47 하라는대로 하면 된다. C. Just K (0:11, +) *528 이것도 지문이 조금 불친절하긴 했는데, 하라는 대로 완전탐색을 돌려주면 맞는다. D. Index Trio (0:30, +2) *983 인덱스가 같을 수도 있어서 식을 좀 생각해서 써주어야 한다. 예제가 앳코더답지 않게 불친절해서 많이들 틀리는 것으로 보였다. E. RLE (1:00, +) *1970 \(DP[i][j]\)를 i번째 글자까지 쓰고, 압축 길이가 ..