NYPC2024 합주 공연 문제 풀이를 진행하였습니다.
NYPC문제는 BIKO를 통하여 풀었습니다
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
N명의 음악가가 모여있고, 편의상 1번부터 N번까지 번호가 매겨져 있으며 음악가는 1번부터 N번가지 순서대로 줄 서 있다.
인간, 엘프, 자이언트 세 종족이 있으며 엘프와 자이언트는 서로 인접하여 있으면 집중을 못 하여 합주할 수 없다.
음악가 중 일부를 제외하여 엘프와 자이언트가 인접하지 않도록 해야 하며, 음익가들이 제외되고 나서 빈자리 없이 서로 붙어서 합주해야 합니다.
엘프와 자이언트가 인접하지 않도록 하기 위해 제외해야 하는 최소 인원 프로그램을 작성해야 합니다.
쿼리 형식으로 입력이 주어진다. 각 쿼리는 (x,v,s,e)의 형태인데, 이는 x번 음악가를 v 종족으로 변경하고, s번부터 e번 음악가만 고려하였을 때 제외해야 하는 최소 인원을 구하라는 의미이다.
문제 풀이
엘프와 자이언트가 인접하면 안되고 딱 붙어서 연주해야 되기 때문에 엘프와 자이언트 중 더 적은 수의 종족을 제외하면 합주가 가능해진다.
엘프와 자이언트 사이에 인간 종족이 있다면 상관없이 합주가 가능해지기에, 인간 종족을 기준으로 엘프와 자이언트만으로 이루어진 구간을 찾아 계산을 진행해야 합니다.
간단하게 배열을 돌아보며 엘프와 자이언트의 값을 더해주고 인간이나 끝에 다다랐을 때 더 적은 종족을 제외시키는 방식으로 하면 손쉽게 답을 찾아낼 수 있지만, 음악가의 수는 최대 1000000이며 주어지는 쿼리의 수 또한 최대 300000개이기 때문에 너무 많은 시간이 걸리게 됩니다.
그래서 각 구간의 합을 빠르게 찾아낼 수 있는 세그먼트 트리를 활용하여 문제를 해결해줍니다.
단순하게 값의 합이 아닌 엘프와 자이언트 두 종족의 합을 알아내야 하므로 struct를 사용해 필요한 데이터의 집합을 만들어 트리를 제작해줍니다.
인간을 기준으로 값이 달라지며 구간에 인간 종족이 없는 경우, 인간 종족이 1명 있는 경우, 인간 종족이 2개 이상 있어 둘 사이의 값이 필요한 경우가 있습니다.
인간의 위치를 따로 저장하고 각 구간을 찾아가며 값을 구하는 것은 많은 시간이 걸립니다. 그러므로 세그먼트 트리 중 "금강 세그먼트 트리"를 사용하여 문제를 해결하였습니다.
그러기 위해서는 많은 정보가 각 정점에 저장되어야 합니다.
인간 종족 = h라고 했을 때
le : h가 나오기 전의 있는 엘프 수
lg : h가 나오기 전의 있는 자이언트 수
re : 마지막 h가 나온 후의 있는 엘프 수
rg : 마지막 h가 나온 후의 있는 자이언트 수
md : h사이의 있는 엘프 수와 자이언트 수(h가 두 개 있을 경우 계산됨)
size : 구간의 크기
ish : h가 있는지 확인
위의 정보를 struct로 만들어 tree로 제작해줍니다.
이후 각 정점의 더하기, 트리 수정, 구간의 합을 알 수 있도록 함수를 만들어주면 됩니다.
전체 코드
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
struct Node
{
//왼쪽 구간의 엘프 수, 왼쪽 구간의 자이언트 수, 오른쪽 구간의 엘프 수, 오른쪽 구간의 자이언트 수, h사이에서 엘프와 자이언트 중 적은 수, 구간의 크기, h존재 여부
int le, lg, re, rg, md, size, ish;
Node() : Node(' ') {}
Node(char c) : Node(c == 'e', c == 'g', c == 'e', c == 'g', 0, 1, c != 'h') {}
Node(int le, int lg, int re, int rg, int md, int size, int ish) : le(le), lg(lg), re(re), rg(rg), md(md), size(size), ish(ish) {}
};
Node operator + (const Node &a, const Node &b)
{
return {
a.le + (a.ish ? b.le : 0),
a.lg + (a.ish ? b.lg : 0),
(b.ish ? a.re : 0) + b.re,
(b.ish ? a.rg : 0) + b.rg,
a.md + b.md + (!a.ish && !b.ish ? min(a.re + b.le, a.rg + b.lg) : 0), //두 노드에 h가 있다면 왼쪽노드의 오른쪽 값과,오른쪽 노드의 왼쪽 값의 엘프와 자이언트의 값을 더하여 적은 값을 추가로 더해줌
a.size + b.size,
a.ish && b.ish
};
}
//세그먼트 트리 초기화
Node TreeInit(vector<Node> & nodeArr, vector<Node> &tree, int node, int start, int end)
{
if (start == end)
return tree[node] = nodeArr[start];
int mid = (start + end) / 2;
return tree[node] = TreeInit(nodeArr, tree, node * 2, start, mid) + TreeInit(nodeArr, tree, node * 2 + 1, mid + 1, end);
}
//일정 범위의 합을 세그먼트 트리를 통해 게산
Node TreeSum(vector<Node>& tree, int node, int start, int end, int left, int right)
{
if (left > end || right < start)
return Node();
if (left <= start && end <= right)
return tree[node];
int mid = (start + end) / 2;
return TreeSum(tree, node * 2, start, mid, left, right) + TreeSum(tree, node * 2 + 1, mid + 1, end, left, right);
}
//세그먼트 트리의 값 수정
void TreeUpdate(vector<Node>& tree, int node, int start, int end, int index, Node diff)
{
if (index < start || index > end)
return;
if (index == start && index == end)
{
tree[node] = diff;
return;
}
int mid = (start + end) / 2;
TreeUpdate(tree, node * 2, start, mid, index, diff);
TreeUpdate(tree, node * 2 + 1, mid + 1, end, index, diff);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
//지정한 위치의 종족 변경
Node ChangeKind(vector<char> &arr, vector<Node> &node, int index, char v)
{
Node n = Node(v);
node[index] = n;
//tree업데이트를 위한 diff를 만들어줌
arr[index] = v;
return n;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> answer;
int N, Q;
cin >> N >> Q;
int h = (int)ceil(log2(N)); //트리의 높이
int treeSize = (1 << (h + 1)); //트리 배열의 크기
vector<char> arr(N + 1);
vector<Node> nodeArr(N + 1);
vector<Node> tree(treeSize);
for (int i = 1; i <= N; i++)
{
cin >> arr[i];
nodeArr[i] = Node(arr[i]);
}
//트리 초기화
TreeInit(nodeArr, tree, 1, 1, N);
Node node = Node();
int x, s, e;
char v;
int changeCount;
//일정 범위에서 제거해야하는 최소 인원을 차례대로 구함
for (int i = 0; i < Q; i++)
{
cin >> x >> v >> s >> e;
if (arr[x] != v)
{
arr[x] = v;
TreeUpdate(tree, 1, 1, N, x, Node(v));
}
node = TreeSum(tree, 1, 1, N, s, e);
cout << node.md + min(node.le, node.lg) + (node.ish ? 0 : min(node.re, node.rg)) << endl;
}
return 0;
}
/* 예제 데이터
4 5
eghg
3 h 1 4
3 e 1 4
2 h 1 3
3 g 2 4
2 e 2 3
5 5
hhheg
3 h 5 5
3 e 1 5
2 g 1 5
3 g 2 4
4 e 1 5
6 5
ehegeh
2 h 1 6
3 g 2 6
6 e 2 6
6 h 1 6
2 e 1 6
*/출저
