본문 바로가기

전체 글

BOJ 16182 - Dumae (D5) 사용 알고리즘Greedy(pq) + Topological Sorting 풀이일단 자명하게 DAG가 아니면 -1이다.그래프의 순서 관계도 있고 [L,R] 조건도 있어서 까다로울 수 있다. 결론부터 말하면 이 둘을 합치면 된다.대충 이런 그래프가 있다고 하자. 여기서 1번 노드는 자기만 보면 1번째 순서가 될 수도 있고 2번째 순서가 될 수도 있다. 하지만 바로 아래 노드(2번)를 고려하면 반드시 1번째 순서가 되어야 함을 알 수 있다. 이 조건을 [L,R]로 표현하려면 어떻게 해야 할까?위 상황에서 \( R_{2} = 2 \)이다. 그 말은 2번 노드는 2번째 순서 안에 선택되어야 한다. 그리고 2번 노드가 선택되려면 1번 노드를 먼저 골랐어야 하므로 적어도 1번 노드는 2번째 순서보다 한칸 앞선 1번째.. 더보기
BOJ 31232 삼국지, BOJ 31750 Split the GSHS 3 (P2,P1) 두 문제는 다음과 같다. 트리에서 간선을 두 개 끊어서 세 컴포넌트로 나눌 때 각각 컴포넌트의 가중치 합을 a,b,c(a 더보기
BOJ 10014 - Traveling Saga Problem (D1) 사용 알고리즘 Centroid Decomposition 풀이 일단 기본 아이디어는 트리와 쿼리 5와 비슷하지만 반대의 기능을 가진 쿼리를 이용한다. 트리와 쿼리 5는 다음과 같은 두 가지 쿼리를 구현해야 한다. 1. 정점 집합에 i번 정점을 추가/삭제한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 가까운 정점과의 거리를 구한다. 여기서 2번 쿼리를 다음과 같이 수정해서 이용한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 먼 정점을 구한다. 비슷해 보이지만 가장 가까운 거리와는 다르게, 가장 먼 거리는 centroid tree 상에서 조상들을 보면서 올라갈 때 같은 서브트리에 속한 정점을 고려하면 거리를 제대로 구하지 못하기 때문에, 자신이 속한 서브트리를 제외하고 가장 먼 거리를.. 더보기
BOJ 24547 - mod와 쿼리 (D4) 사용 알고리즘 Segment Tree, Sqrt Decomposition, Number Theory(Harmonic Lemma) 풀이 쿼리 1번은 잘못 보면 그냥 단순한 합 문제로 보이지만, 시그마 안에 mod가 있어서 단순한 문제는 아니라는 걸 알 수 있다. (이 사실을 코드 짜고 예제 1번 돌려보기 전까지 몰랐다.) 하지만 그렇게 어려운 문제도 아니다(?). X의 범위에 따라 나눠서 처리하면 되는데, X 316일때는 크기 X칸의 버킷에 따라 mod X할 때 빼야하는 X의 개수가 다르다는 점을 이용해 O(10^5/X)에 처리할 수 있다. 쿼리 2번은 좀 더 복잡하다. 일단 mod의 정의를 이용해 단순화해보면 이 쿼리는 \( nX - \sum A_{i} * \left \lfloor \frac{X}{A_{.. 더보기
Codeforces Round 930 (Div.2) (+퍼플 달성) 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 +) A 문제가 복잡하게 써져 있지만 결국 1번 위치만 본다면, 1->2로 가고 2->4로 가고... 임을 알 수 있다. 따라서 n 이하인 가장 큰 2^k까지 간다. 참고로 이것과 매우 유사한 문제가 흐즈로컵 3회에 있었는데, 그 이유는 이 문제 출제자가 흐즈로컵 출제자이기 때문이다. 더보기 #include using namespace std; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define comp(x) x.e.. 더보기
2월 PS (3) 이번 주는 글을 미리미리 안써놔서 몰아쓰는 관계로 내용이 부실할 수 있다. 또한 날짜별 분류가 큰 의미가 없는 것 같아 앞으로는 구분하지 않겠다. POI'12/13 레이저 solved.ac 티어 더보기 20240212 기준 : Platinum I (μ = P1 - 0.16, σ = 0.38) 알고리즘 분류 더보기 solved.ac : dp, coordinate_compression, prefix_sum, sweeping, geometry 작성자 풀이 : dp, coordinate_compression, prefix_sum, sweeping, geometry, segtree(lazyprop) 풀이 더보기 원점에서 쏘는 직선의 기울기를 0에서 쭉 증가시킨다고 해보자. 그러면 직선이 레이저에 맞는 기울기가 구.. 더보기
BOJ 21099 - Four XOR (P4) 사용 알고리즘 Pigeon Principle, Brute Force 풀이 A,B,C,D는 대충 배열에서 서로 다른 4개를 뽑은 값이라 하자. A xor B xor C xor D = 0이므로 A xor B = C xor D를 얻는다. 즉 두 수를 xor한 값이 같은 순서쌍이 존재하는지 판별하는 문제와 동치이다. 그럼 이제 이걸 어떻게 푸느냐? 를 고민하면 굉장히 어렵다. 적어도 O(Nlog^2N) 정도에는 해야할 것 같은데 쉽지 않다. 아니 애초에 A xor B = k인 거 찾기도 O(NlogN) 정도는 걸린다. 그런데 사실 이건 함정이다. 고민하다 보면, 가능한 순서쌍 개수는 O(N^2)개인데 이게 다 다를 수 있는가? 에 대한 의문을 가지게 된다. 한번 생각해보자. 수 범위가 10^5 이하이므로 xor.. 더보기
2월 PS (2) 티스토리에 서식이 있는 걸 발견했다. 개꿀 2/5 이 글에 있는 문제 위주로 풀었다. BOJ 22306 트리의 색깔과 쿼리 2 트리의 색깔과 쿼리를 온라인으로 처리하는 문제이다. solved.ac 티어 더보기 20240205 기준 : Diamond IV (μ = D4 - 0.23, σ = 0.44) 알고리즘 분류 더보기 solved.ac : smaller_to_larger, hash_set, tree_set, graph_traversal 작성자 풀이 : smaller_to_larger, tree_set, graph_traversal 풀이 더보기 말 그대로 간선을 직접 끊을 것이다. 이를 위해 인접 리스트는 std::set으로 관리한다. 간선을 끊으면 2개의 컴포넌트로 나뉘어질 것인데, 이 중 크기가 더 .. 더보기

티스토리툴바