취미로PS하는사람

퍼플따리라서 에듀가 rated contest이다. 후... C에서 좀 말려서 E를 그렇게 늦게 풀지 않았음에도 랭킹이 상당히 낮았다. 앳코더를 열심히 해서 그런지 코너 케이스나 기타처리가 좀 미숙해졌다는 걸 느꼈다. 구현실력도 줄어들고. 코포도 레드 찍기로 마음 먹었으니 힘을 더 내야겠다. 오늘 풀지 못한 F는 정수론 문제로 보였는데, 내가 정수론을 잘 몰라 정수론 문제가 나올 때마다 숨이 턱턱 막힌다. 날잡고 정수론 웰노운이나 유용한 알고리즘들을 배워야겠다. 특히 디리클레 합성곱인가 그거.. 그거 꼭 배워야지 https://codeforces.com/contest/1622 A 막대 3개가 있는데 하나를 부러뜨려서 직사각형을 만들 수 있는지 판별하는 문제다. 일반성을 잃지 않고 $a \leq b \leq..

앳코더 2000이 되니 rated contest가 ARC밖에 없어서(사실상 AGC는 한두달에 한번이니) 요즘 좀 심심했다. ABC도 각잡고 풀면 좋을텐데 rated가 아니다보니 난이도 2400 내외의 한두문제 보고 풀이 떠올리고 이정도 이상은 귀찮아서 안 하게 되더라. 아무튼 오늘 간만에 앳코더를 쳤고, 퍼포 2330정도로 나름 선방한 것 같다. 앳코더를 볼수록 생각하는 힘은 길러지는데 코딩은 점점 느려지는 것 같다 ㅋㅋ! https://atcoder.jp/contests/arc132/tasks A 두 배열 $R$, $C$가 주어진다. $i$번째 열에는 $R_i$개의 #이, $j$번째 행에는 $C_j$개의 #이 있도록 격자가 채워진다. 각 위치에 대해 #인지 아닌지 판별하는 문제다. $i, j$가 주어졌..

https://www.acmicpc.net/problem/13329 팀연습에서 맞춘 문제 중 가장 어려운 문제가 아닐까 싶다. 정확히 말하면 맞추지는 못했고 풀이를 낸 이후에 코딩을 완성하지 못했다가, 조금만 손 보고 맞았다. 문제 y좌표가 모두 0보다 큰 영역에 대해, 컨벡스 헐이 $N$개 있다. $(0, 0)$에서 볼 수 없는 컨벡스 헐의 개수는? 풀이 더보기 우선 생각할 점은, 하나의 컨벡스 헐은 그 컨벡스 헐의 점 중 각도가 가장 큰 것과 작은 것의 선분으로 대체할 수 있다는 것이다. 문제에서 컨벡스 헐이 겹치지 않는다고도 했으니.. 아무튼 이 처리를 하고 나면 이 문제는 볼 수 없는 선분의 개수를 세는 문제로 바뀐다. 이 때 어떤 선분을 볼 수 없으려면, 그 선분이 커버하는 각도를 다른 선분들이..

https://www.acmicpc.net/problem/12876 일차함수 $y=a_ix+b_i$들의 최댓값에 대해 생각해보자. 잘 생각해보면, 최댓값을 이루는 직선들의 기울기는 $x$좌표가 증가하며 단조증가함을 알 수 있다. 만약 단조증가하지 않는다면, 기울기가 감소하게 된 직선의 이전의 직선이 더 큰 함수값을 가지므로 모순이 된다. 따라서, CHT를 짜듯이 된다. 다만 입력으로 들어오는 직선의 기울기의 단조성이 없고, 삽입과 삭제가 있다. 때문에 적당한 이분탐색과 set으로 직선들을 관리해야 한다. 하지만 우리에게는 더 무지성을 지향할 수 있는 자료구조가 있다. 바로 리차오 세그먼트 트리이다. 어떤 구간의 중앙값에서 가장 함숫값이 큰 함수에 대해 생각하자. 이를 그 구간을 대표하는 직선이라고 하자...

https://www.acmicpc.net/problem/17642 센트로이드 분할과 레이지 세그를 이용한다면 이론적으로는 풀 수 있다. 하지만 그걸 언제 구현하고 앉았는가... 오일러 투어 순서를 나열해보자. 그리고 그 사이에 간선의 가중치를, 내려갈 때는 +, 올라갈 때는 -로 생각해보면..? 정점 $x$와 정점 $y$사이의 경로는 오일러 투어 상에서 $x$가 맨 처음 등장하는 위치를 $s_x$라 할 때 대략 $s_{x}$~$s_{y}$의 구간의 가중치를 적당히 더하고 뺀 값과 같게 된다. 정확히는, 구간을 두 개로 쪼개 앞쪽은 모두 빼고 뒤쪽은 모두 더한 결과의 최댓값과 같게 된다. 그 이유는, 우선 실제 경로상에 포함되지 않는 경로의 경우 내려갔다와 올라갔다와 모두 포함되기 때문에 상쇄되어 0이 ..