cheetose 의 PS

요즘 맨날 OI 문제만 풀다보니까 머리가 빠르게 안돌아가고 코딩 속도가 상당히 느려짐을 느껴버렸다. 모 슬랙 덕분에 이 셋을 알게 됐고 solved.ac 기준 절반 이상이 플래티넘 수준의 문제라 스피드런 연습하기 좋아보인다고 판단해서 돌았다. https://codeforces.com/gym/102433 여기랑 https://www.acmicpc.net/category/detail/2131 여기에서 풀 수 있다. 결과는 9솔. B에서 말린 것과 추후에 설명할 서버폭파 코포가 코포함 만 아니었어도 패널티 관리는 매우 좋았을 수도..? 앞으로 쭉 나열할 타임라인에서 자세한 풀이는 안쓰고 문제를 풀면서 들었던 생각들을 적을 예정입니다만 강력한 힌트도 존재하기 때문에 접어두겠습니다. D - Dividing By ..

https://www.acmicpc.net/problem/15555 2018 일본 정올 기출문제로, 상당히 재밌는 문제다. 가장 먼저 할 수 있는 쉬운 관찰은 세로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없고, 가로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없다는 것이다. 이를 이용해서 서로 겹치는 세로 스틱과 가로 스틱 쌍으로 이분 그래프를 만들 수 있고, 쾨니그 정리를 이용하면 쉽게 풀 수 있으나 정점의 수가 3000*3000이라 어림도 없다는 걸 바로 깨달았다. 여기서 하나의 관찰을 더 해야한다. 조금 더 쉽게하기 위해 중앙의 G를 기준으로 스틱을 판단해본다고 하자. 어떤 스틱의 G의 좌표가 $(i,j)$라고 하면, 이 스틱과 겹칠 수 있는 다른 스틱의 G의 좌표는 $(x,y), x+y=i+j..

지난주 알프스 내부대회에 이어 18, 19일 이틀간 숭고한 알고리즘 대회를 진행했다. 기도를 해야할 거 같은 굉장히 성스러워보이는 이름이지만 3년째 이어오고 있는 숭실대, 고려대, 한양대 연합 대회다. 지난 2년간은 알고리즘 캠프 4일 + 대회 1일로 이루어졌었는데 올해는 코로나로 인해 대회만 진행했다. 여기에서 문제를 풀어볼 수 있고 (코드포스), 지문 및 풀이는 여기에서 확인 가능하다. 내가 낸 문제는 Advanced I. 찾아라 드래곤볼!, Marathon J. 3N 투어링, Marathon M. 리그 오브 숭고한, 이렇게 총 3문제다. 찾아라 드래곤볼 문제는 대충 HLD와 Lazy propagation과 sparse table과 euler tour technique을 짬뽕시킨 희대의 쓰레기 문제다..