본문 바로가기

백준/다이아

BOJ 17187 - Necklace (P1), BOJ 22195 - Necklace 4 (D5) 둘은 메모리 제한만 다른 문제이다. 사용 알고리즘더보기kmp 풀이더보기두 문자열을 s, t라 하자. 뒤집는 경우는 s든 t든 하나만 뒤집고 똑같이 하면 되니 뒤집는 경우는 고려하지 않아도 된다.t = A+B로 쪼개고 r = B + '$' + s + '#' + A 꼴로 된 문자열을 생각해보자. 중간에 $와 #는 문자열을 구분짓기 위한 dummy이다.예를 들어, s = "yxbadctz", t = "dcbayxz"일 때 A = "dc", B = "bayxz"가 가능하다.r = "baxyz$yxbadctz#dc"가 된다. 이제 여기서 r의 fail function과 rev(r)의 fail function을 구한 다음 $와 # 사이에 있는 인덱스 i를 순회하면서 fail_r{i} + fail_rev(r){|r|.. 더보기
BOJ 18083 - Disposable Switches (D5) 지금까지 푼 CHT 문제들 중에 CHT를 가장 특이하게 쓰는 것 같다. 사용 알고리즘dp, Convex Hull Trick 풀이가장 먼저 관찰해야 하는 사실은 v가 영향을 줄 수 없다는 것이다. 왜냐하면 v>0이므로 처음부터 v가 나눠져 있었다고 생각하면 된다.결국 각 간선의 가중치는 l + c가 되고, 최단 경로의 간선 개수에 영향을 받음을 알 수 있다. 이제 다음과 같은 dp를 정의하자.dp[i][j] := 1번 정점에서 i번 정점까지 도달하는 데에 j개의 간선을 사용했을 때의 최단 경로이는 O(N(N+M))에 계산할 수 있다. (다익스트라를 이용한 O(N(N+M)logNM)은 TLE를 받는다.)이렇게 구한 dp[n][i](1 f_i(x) = i*x + dp[n][i]라는 직선을 생각해보자. 이 직.. 더보기
BOJ 16182 - Dumae (D5) 사용 알고리즘Greedy(pq) + Topological Sorting 풀이일단 자명하게 DAG가 아니면 -1이다.그래프의 순서 관계도 있고 [L,R] 조건도 있어서 까다로울 수 있다. 결론부터 말하면 이 둘을 합치면 된다.대충 이런 그래프가 있다고 하자. 여기서 1번 노드는 자기만 보면 1번째 순서가 될 수도 있고 2번째 순서가 될 수도 있다. 하지만 바로 아래 노드(2번)를 고려하면 반드시 1번째 순서가 되어야 함을 알 수 있다. 이 조건을 [L,R]로 표현하려면 어떻게 해야 할까?위 상황에서 R2=2이다. 그 말은 2번 노드는 2번째 순서 안에 선택되어야 한다. 그리고 2번 노드가 선택되려면 1번 노드를 먼저 골랐어야 하므로 적어도 1번 노드는 2번째 순서보다 한칸 앞선 1번째.. 더보기
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_{.. 더보기
BOJ 16901 - XOR MST (D4) 본인 풀이로 푼 사람이 없는 것 같아서 써 본다. 알고리즘 분류 Union Find, Trie(xor minimization/update), MST(idea) 풀이 일단 생각을 해보자. 일단 크루스칼 알고리즘 기준으로 생각해보면, 아직 하나도 병합되지 않은 정점이 처음 병합될 때, 당연히 가중치가 최소인 간선을 통해 병합될 것이다. 그럼 얘를 찾아주자. 가중치가 XOR이므로 자신을 제외한 정점 중 xor했을 때 최소인 정점과 연결해야 할 것이다. 이는 Trie를 이용하면 O(비트 개수)에 찾을 수 있다는 사실이 알려져 있다. 일단 이 과정을 모든 정점에 대해 한번 반복했다고 하자. 여기서 2가지 관찰을 할 수 있다. 1. 한 번 병합된 컴포넌트들을 다시 하나의 정점 그룹으로 생각하면, 각 정점 그룹에서도.. 더보기
BOJ 3654 - L퍼즐 (D4) 사용 알고리즘 Bipartite Matching 풀이 L을 가로 일자랑 세로 일자로 분리해서 생각해보자. 그럼 결국 검정색 하나를 기준으로 흰색 2개가 가로에 최대 1개, 세로에 최대 1개 붙을 수 있다. 이를 이용해 이분 그래프를 만들고 이분매칭을 해서 전체가 매칭되는지 확인하면 된다. BOJ는 hopcroft-karp로 냈는데 코드가 길어서 여기서는 일반 이분매칭 코드를 올린다. 더보기 #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 com.. 더보기
BOJ 18798 - OR과 쿼리 (D5) 사용 알고리즘 풀이 1 : Fenwick Tree + Segment Tree (binary search) + Offline Query + fastIO (O(30NlogN)) 풀이 2 : Fenwick Tree + Segment Tree (bitwise AND) (O(30N + NlogN)) 풀이 1 이 풀이의 기본 아이디어는 KOI'23 고기 파티 문제 풀이를 기반으로 한다. 모든 수들은 1번 쿼리에 의해서 어떤 시점에서 K가 되었다가 다시 K가 아니게 된다. OR 연산이 단조성을 띄므로 이 K가 되는 구간은 연속하게 된다. 그래서 모든 수에 대해서 이 시점을 기록한 후, 이를 나중에 쭉 처리하는 아이디어를 이용한다. 1번 쿼리에 순서대로 번호를 붙이자. 이제 i=1~n에 대하여 Ai가 언제 K가 되는.. 더보기

티스토리툴바