leo020630의 블로그

ABC랑 코포 Div.2를 쳤다. ABC 256 A. 2^N (0:00, +) *7 이건 좀.. B. Batters (0:03, +1) *83 하라는 대로 구현해주면 된다. 이상하게 읽었다가 한번 틀렸다. C. Filling 3x3 array (0:08, +) *541 좌상단 4개의 숫자만 정해주면 나머지는 모두 자동으로 정해진다. 따라서 \(O(30^4)\)에 문제를 해결할 수 있다. D. Union of Interval (0:11, +) *546 백준에 널린 스위핑 기본 문제 E. Takahashi's Anguish (0:18, +) *1224 Functional Graph 형태이니 그림을 그려주자. 일자 형태는 잘 배치할 수 있는데, 사이클 형태는 하나를 끊어서 일자로 만들어주어야 한다. 이 때, ..

화~수는 조별 과제 + 귀가 때문에 랜덤 디펜스를 하지 못했고, 어제는 문제를 뽑았더니 코포가 얼마 남지 않았길래 하나만 풀고 코포하러 갔다. 코포는 대차게 망했다. 전혀 틀린 점이 없는 코드들이 틀리길래 억울해 하던 중, 대회 시작 1시간 후 이런 걸 발견했다. 원래 long long으로 고정해 두는데, 백준 풀면서 바꾼걸 까먹었던 것이다. 이후 1시간동안 C를 푸려고 노력해보았으나 잘 되지 않았고, 그대로 퍼플로 향했다. 16~17일에 랜플디로 고른 문제들은 아래와 같다. 5480 - 전함 온라인으로 해결하는 것은 어려워 보이니, 오프라인으로 해결하는 방법을 떠올려보자. 2차원일 때와 1차원일 때의 풀이 방법이 크게 다르지 않으므로 1차원이라고 가정하자. 이 때, 한 가지 관찰이 필요하다. : 나를 ..

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을 만들기 위해서 몇 가지 생각해야 할 부분이 존재..

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

셋은 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 도로 정비하기 랜덤으로 걸린 문제이다. 각 도로..