thisisuser's study

11011번: Forged Answers (acmicpc.net)solved.ac: Gold I (2024.09.13) 아이디어 하나가 필요한 그리디 문제입니다. 문제를 요약하면, 답지를 조작해서 세 사람의 점수 중 가장 낮은 값을 최대로 끌어올리는 문제입니다.다음과 같이 각 문제를 분류할 수 있습니다.세 사람 다 동일한 답안을 낸 경우두 사람이 동일한 답안을 내고, 한 사람은 다른 답안을 낸 경우세 사람 모두 다른 답안을 낸 경우1번의 경우, 당연히 다 맞게 하는 게 최적입니다. 이는 너무나 자명합니다.3번의 경우 원하는 사람의 점수를 1 올릴 수 있습니다. 2번의 경우가 조금 특이합니다. 여기서는 두 사람의 점수를 1 올리거나, 한 사람의 점수를 1 올릴 수 있습니다.일단 솔직히 좀 난해합니다. 다음..

13576번: Prefix와 Suffix (acmicpc.net) solved.ac: Platinum II (2024.09.10) 꽤나 흥미롭게 풀었던 문제입니다.배울 점이 많은 문제라고 생각합니다. 1. Prefix이자 Suffix인 substr 구하기처음엔 전체 문자열 하나 잡고, 앞으로 계속 lcp랑 len이랑 다를 때까지 탐색하면 되지 않을 까 생각했습니다.그러나 BBAABB같은 문자열을 생각해 보면, 씨알도 안 먹히는 소리임을 알 수 있습니다. 처음엔 쌩 SA + LCP만 가지고 풀어보려 했으나, 능지 이슈로 이건 아직도 모르겠습니다.그래서 그냥 실패함수 가져다 썼습니다. 조건을 만족시키는 substr의 길이는 fail(len)을 반복적으로 수행하여 얻을 수 있습니다. 2. 그래서 문자열 나타는..

19651번: 수열과 쿼리 39 (acmicpc.net)solved.ac: Diamond V (2024.09.06) 나이브하게 처리하는 것은 상당히 노답이므로, 문제를 변형시킬 필요가 있습니다.등차수열에서 주로 사용되는 성질로 A[i-1] + A[i+1] = 2A[i]를 이용합시다. 새로운 배열을 생각해서 B[i] = A[i-1] + A[i+1] - 2A[i]이라 하면,세 수 A[i-1], A[i], A[i+1]가 등차수열을 이룰 시 B[i] = 0이 됩니다.따라서 쿼리의 답은 (연속해서 0인 B[i]의 개수) + 2가 됩니다. 이는 금광세그 트릭을 이용하면 구할 수 있습니다. 업데이트의 경우 세 수가 모두 포함되거나 포함되지 않을 경우 변화량은 없으므로,쿼리 [s, e]에 대해 B[s - 1], B[s..

12963번: 달리기 (acmicpc.net)solved.ac: Platinum 3 (2024.09.06) 플로우 안 쓰는 플로우 문제입니다.일단 문제를 딱 보자마자 최대 유량 문제구나를 파악할 수 있는데 범위가 노답입니다. 최대 유량을 구하는 문제이므로 최소 컷을 구해야 함을 알 수 있습니다.이때 용량이 특수하게 주어지므로, 다음을 이용합시다.1. 최대 유량을 흘렸을 때, 유량이 존재하는 간선을 모두 제거하면 보낼 수 있는 유량은 0이다.2. i번 간선에 유량이 흐른다면 이 유량으로 0번부터 i-1번 간선에 모두 유량을 보낼 수 있다. 0번 간선에서 N-1번 간선까지의 어떠한 경로가 존재한다면, 유량은 당연히 가장 작은 간선의 용량이 될 것입니다.또한 2번에 의해, 여러 개의 경로가 존재할 때 일부 간..

솔직히 왜 골드2인지 모르겠는 문제. 간단한 트리 DP?를 통해 해결했다.문제solved.ac: Gold II (2024.09.06) 어차피 식을 모두 합치면, (a1 + a2 + ... ) - (b1 + b2 + ... ) 꼴이 될 것이다.따라서 최대한 작은 수들을 빼면 된다. 이건 정렬 + 그리디로 된다. 어떤 서브트리와 두 서브트리에서 빼야 하는 노드의 개수를 각각 A, B개라 하자.만약 현재 노드가 +라면, 이 서브트리에서 빼야 하는 노드의 개수는 자명히 A + B개가 된다. 반면 현재 노드가 -라면, 원래 빼야 했던 노드는 다 더해지고, 원래 더해야 했던 노드들이 빼지게 된다.따라서 우측 서브트리의 트리 크기를 sz라 하면, 빼야 하는 노드의 개수는 A + (sz - B)개가 된다. 그러면 총 ..

11378번: 열혈강호 4 (acmicpc.net)solved.ac: Platinum III (2024.09.10) 문제에서 시키는 대로 모델링하고 맞을 수 있다.모델링 방법이 조금씩 다른 것 같긴 하다. 본인은 다음과 같이 모델링했다.#include #include #include #include using namespace std;const int INF = 1e9;vector node[2005];int capacity[2005][2005];int flow[2005][2005];int networkFlow(int source, int sink){ int res = 0; int parent[2005]; while(1) { memset(parent, -1, sizeof(parent))..

1867번: 돌멩이 제거 (acmicpc.net)solved.ac: Platinum III (2024.09.10)a행 b열에 놓인 돌멩이를 제거하기 위해서는 a행을 쓸거나 b열을 쓸어야 한다.  그래프로 환원시키면, 1~n행과 1~m행 정점을 만들어 놓고,간선을 돌로 정의해서, 해당 간선이 잇는 두 정점 중 하나가 색칠되면 된다라고 할 수 있다.여기서는 1행을 쓸고, 2열을 쓸면 된다. 그래프로 나타내면, 다음과 같다. 즉, 문제를 재정의하면 이분 그래프에서 최소한의 정점으로 모든 간선을 칠하는 방법을 찾는 문제가 된다.이는 최소 정점 커버 문제 (Minimum Vertex Cover)로 알려져 있고, 이분 그래프의 경우 다항 시간 해법이 존재한다.결론부터 말하면, 이분 그래프에서 최소 정점 커버의 해답..

11012번: Egg (acmicpc.net)solved.ac: Platinum II (2024.09.10)각 직사각형별로 경계 또는 내부에 있는 점의 수를 세어 더하는 문제다. 일단 직사각형을 하나씩 구해 보는 건 당연히 불가능할 것임을 짐작할 수 있다.조금 생각을 바꿔서, 각 점별로 세지는 횟수를 구해 보자. 점별로 구하기 위해서는, 해당 점에 몇 개의 직사각형이 겹쳐 있는 지 파악해야 한다.왼쪽부터 훑으면서 직사각형을 관리하는 것은 스위핑 기법이 잘 알려져 있다.다음과 같이 직사각형의 시작과 끝을 구분해 보자. 푸른 색이 새로운 직사각형 시작, 빨간 색이 직사각형 끝이다.이제 왼쪽부터 스위핑을 하면서, 구간 업데이트를 통해 해당 위치에서의 직사각형 개수를 구하면 된다.이는 lazyprop 세그트리를..

https://www.acmicpc.net/problem/7626solved.ac: Platinum I (2024.09.10)직사각형이 여러 개가 주어질 때 합집합의 넓이를 구하라는 문제다.참 별 게 다 웰노운이다 싶다. 일단 x축 기준으로 쭉 정렬한 다음, 세로 선분들을 관리해주고 대충 스위핑질해주는 풀이이다. 세그먼트 트리 사용이 조금 특이하긴 하다. 두 가지 변수를 관리해주는데, 구간별 누적 길이랑 전체를 덮은 횟수를 기록해 준다.전체를 덮은 횟수가 1 이상이라면 해당 구간의 값은 전체 길이와 동일하다.그렇지 않다면 두 자식 노드로 쪼개고 그 합을 구하여 해결한다. 범위가 크니 좌표 압축을 해 주어야 한다.딱히 쓸 게 없네요#include #include #include #include using ..

간단히 말해 트라이 위에서 KMP를 수행하는 알고리즘이다.짤막하게 트라이와 KMP를 짚어보고 넘어가겠다. 1. 트라이(Trie)N개의 길이 M 문자열 리스트가 있을 때, 어떤 문자열이 해당 리스트에 포함되어 있는 지 판단하는 알고리즘을 짠다고 하자.Naive하게 짜면 $O(NM)$일 것이고, 여기서 더 줄일 수 있는 방법은 딱히 없어 보인다.(정렬을 하면 $O(MlogN)$으로 줄어들긴 하겠지만, 그 과정이 애초에 비효율적이다.) 트라이는 트리 자료구조에서 착안하여, 무려 $O(M)$에 찾을 수 있도록 구성해준 것이다.기본적으로 다음과 같이, 트리를 따라 리프 노드까지 쭉 따라가면서 순서대로 합친 것을 문자열로 생각한다.보통 포인터를 활용하여 구성한다. 아래는 트라이 코드의 일부이다.더보기struct n..