0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다.
일반적으로 O(NM) 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 x로 갈 수 있고, x에서 0번 도시로 올 수도 있는 x들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 O(NM)만에 확인해주면 된다.
트리가 주어지고, 각 노드마다 구슬이 여러 개 있을 수 있다. 두 명이서 게임을 하는데, 각 차례마다 구슬 하나를 선택해 구슬이 있는 노드의 자식 노드로 움직일 수 있다. 만약 자기 차례에 더 이상 움직일 수 있는 구슬이 하나도 없는 경우 진다. 두 명 모두 최적의 전략으로 게임에 임할 때, 누가 이기는지 구하는 문제다.
주어진 트리에서 노드 별로 Grundy Number를 구한다. 각 구슬마다 자신이 있는 노드의 Grundy Number를 XOR 했을 때 결과가 0이면 처음 시작하는 사람이 지고, 0이 아니면 처음 시작하는 사람이 이긴다. 각 노드에 있는 구슬의 개수가 많지만, 구슬 개수의 홀짝성을 이용하면 쉬워진다.
문제에서 가능한 Grundy Number는 최대 14다. 트리 구성에서 노드의 Grundy Number가 g이기 위해서 그 노드의 서브 트리에 있는 노드 개수가 최소 2g개 필요하기 때문이다.
정점이 N개고 간선이 M개인 무방향성 그래프가 주어진다. 이 그래프에서 정점 3개를 선택하는데 선택 된 저점들이 서로 연결이 되어 있지 않은 것의 개수를 세는 문제다.
처음으로 O(NM) 방법을 생각할 수 있다. 문제 데이터는 O(NM) 방법보다 빠른 방법을 요구한다. 우선, 문제를 역으로 생각해서 간선이 적어도 하나라도 연결되어 있는 세 정점을 찾는 것으로 바꾼다. 그리고 차례대로 3개의 간선으로 연결되어 있는 세 정점 개수, 간선 2개로 연결되어 있는 세 정점 개수, 간선 1개로 연결되어 있는 세 정점 개수를 센다.
간선 3개로 연결되어 있는 세 정점의 개수는 그래프에서 그려지는 삼각형의 개수와 같다. 이 개수를 O(M1.5)으로 구할 수 있다.
우선 N≤5000이므로 임의의 두 점 사이에 간선이 연결되어 있는지 배열을 이용하여 O(1)만에 구할 수 있다. 차수가 √M 이상인 정점들을 무거운 정점이라 하자. 무거운 정점의 개수는 √M 이하다. 무거운 정점 3개로 이루어진 삼각형은 (√M)3=O(M1.5)으로 해결 가능하다. 마찬가지로 무거운 간선을 정의할 수 있는데, 무거운 정점 두 개를 연결하는 간선을 무거운 간선이라 부르자.
무거운 간선이 아닌 간선이 연결하는 두 정점 a, b 중 차수가 작은 정점을 a라 하자. 정의에 따라 a는 무거운 정점이 아니다. 때문에 a의 차수는 √M 이하다. 이제 이 간선과 a에 연결된 다른 간선들을 모두 묶어보고 삼각형이 되는지 확인하면 된다. 이 시간복잡도도 M×√M=O(M1.5)가 된다.
이제 간선 2개로 연결되어 있는 세 정점의 개수는 O(N) 만에 구할 수 있다. 차수가 d인 정점 i를 포함한 간선 2개로 이루어질 수 있는 세 점의 개수는 (d2)가 된다. 이를 다 더한다. 이 중에 삼각형이 있을 수 있는데, 더한 값을 삼각형 개수에 비례하게 뺀다.
마찬가지로 간선 1개로 연결되어 있는 세 정점의 개수도 O(N) 만에 구할 수 있다. 차수가 d인 정점 i를 포함한 간선 1개로 이루어질 수 있는 세점의 개수는 d×(N−d−1)이다. 이를 다 더한 뒤, 앞에서 구한 간선 2개로 이루어질 수 있는 세 점 개수에 비례하여 값을 빼주면 된다.
if(V[i].substr(V[i].length()-2) == V[i+2].substr(V[i+2].length()-2)) B += 20;
if(syl[i] == syl[i+2]) C += 10;
}
printf("%d %d %d %d %d\n", A, B, C, D, A+B+C-D);
}
}
G. Hari Merdeka
N개의 알파벳이 주어지고, 각 알파벳을 쓰는데 비용이 주어진다. M개의 단어가 주어지고, 각 단어마다 문장에 등장 했을 때 얻는 점수가 주어진다. 쓰는데 비용 B를 넘지 않는 문장을 쓸 때, 단어 등장 점수의 합이 최대가 되는 문장의 점수를 구하는 문제다.
문제에서 주어지는 단어들을 가지고 Aho-Corasic Trie를 만들면 노드 개수가 최대 10,000개가 된다. Dynamic Programming으로 각 Aho-Corasic의 상태별로 돈을 b 만큼 썼을 때 얻을 수 있는 최대 점수를 구한다. 총 시간복잡도는 O(NM|W|B)가 된다.
S개의 정점과 L개의 간선으로 이루어진 무방향성 그래프가 주어진다. 각 간선에는 길이가 있다. 간선에 카메라를 설치할 때, 설치 비용은 간선 길이와 같다. 그래프에서 모든 싸이클에 대해 싸이클에 속한 간선 중 적어도 하나에는 카메라를 설치하고 싶다. 이 때 카메라를 설치하는 최소 비용을 구하는 문제다.
어떤 간선에 카메라를 설치하면 그 간선이 포함된 싸이클에 대해서는 문제의 조건을 만족시켜준다. 따라서 카메라를 설치한 간선들을 다 지웠을 때 그래프에 싸이클이 존재하지 않으면 된다. 이제 문제는 전체 그래프에서 Maximum Spanning Tree를 구하는 것과 같다.
intfind(intn){ returnpar[n] == n ? n : (par[n] = find(par[n])); }
intmain()
{
intts = 0, i, j;
for(scanf("%d", &T);T--;){
printf("Case #%d: ", ++ts);
scanf("%d%d", &N, &M);
intans = 0, ans2 = -1;
for(i=1;i<=M;i++) scanf("%d%d%d", S+i, E+i, C+i), num[i] = i, ans += C[i];
for(i=1;i<=N;i++) par[i] = i;
sort(num+1, num+M+1, cmp);
intcnt = 0;
for(i=1;i<=M;i++){
intx = num[i];
inta = find(S[x]), b = find(E[x]);
if(a == b){
if(ans2 < 0) ans2 = C[x];
continue;
}
par[b] = a; ans -= C[x];
}
printf("%d %d\n", ans, ans2);
}
}
I. Best Position
'G'(grain)와 'L'(livestock) 두 문자로 이루어진 R×C 크기의 직사각형이 있다. 마찬가지로 H×W 크기의 작은 직사각형이 주어진다. 작은 직사각형을 전체 직사각형에 뒤집지 않고 같은 문자의 개수가 최대화 되게 배치하는 문제다.
이 문제는 FFT(Fast Fuorier Transform, 고속 푸리에 변환)으로 해결할 수 있다. 큰 직사각형을 RC 크기의 이진수열로 나타내는데, 위치에 있는 값이 'G'인 경우 1, 아닌 경우 0으로 나타낸다. 마찬가지의 규칙으로 작은 직사각형에 대해서는 (H−1)C+W 크기의 이진수열로 나타낸다. 그런 뒤 FFT를 통해 convolution을 구하면 각 부분직사각형 위치마다 매치되는 'G'의 개수를 구할 수 있다. 마찬가지로 각 부분직사각형 위치마다 매치되는 'L'의 개수를 구할 수 있다. 시간복잡도는 테스트케이스별로 O(RClgRC)다.
unsigned t = (A >> i) | ((A & ((1 << i)-1)) << (32-i));
if(t != B) continue;
if(right > i) right = i;
if(left > 32-i) left = 32-i;
}
if(right < left) printf("%d Right\n", right);
elseif(right > left) printf("%d Left\n", left);
else{
if(right == 32) puts("Not possible");
elseprintf("%d Any\n", left);
}
}
}
K. Ball
'W' (White), 'R' (Red), 'G' (Green) 중 하나의 색으로 색칠되어있는 공 L개가 원형으로 배치되어 있다. 단위 시간이 지나면 특정 규칙에 따라 공의 색이 변한다. 단위 시간 N이 지났을 때, 각 색 별로 공이 몇 개 있는지 구하는 문제다.
'W'를 0, 'R'을 1, 'G'를 2로 나타내자. 그러면 단위 시간이 지났을 때 변하게 되는 공의 색은 (자기 색 + 오른쪽 공의 색)을 3으로 나눈 나머지가 된다. 현재 색을 ai(0≤i<L)로 나타내자. 단위 시간이 한 번 지났을 때 공의 색을 bi로 나타내면 bi=ai+ai+1이 된다.
단위 시간이 세 번 지났을 때 공의 색을 ci로 나타내면 ci=ai+3ai+1+3ai+2+ai+3가 된다. 이를 3으로 나눈 나머지이므로 정리하면 ci=ai+ai+3이 된다.
마찬가지로 단위 시간이 아홉 번 지났을 때 공의 색을 di로 나타내면 di=ai+ai+9가 된다. 그렇다는 것은 단위 시간이 3k번 지난 이후 i번 공의 색은 ai+ai+3k가 된다는 것이다. 이를 통해 단위 시간 N이 지났을 때 공의 색을 O(LlogN) 만에 구할 수 있다.