JOISC 2021/2022

Day 1.

 

Jail

 

트리 형태의 감옥이 주어진다. 이후 M개의 죄수의 초기 위치인 a_i와, 목표 위치인 b_i가 주어진다.

죄수를 인접한 위치로 옮길 수 있다. 다음 두 조건을 만족하면서 M개의 죄수를 목표 위치로 옮길 수 있는지 판별하면 된다.

1. 도중에 한 방에 여러 명의 죄수가 존재해선 안 된다.

2. 한 죄수는 무조건 최단경로로만 이동해야 한다. (트리이므로 최단경로가 유일하다.)

 

다음과 같은 관찰이 가능하다.

Claim) 만약 가능하다면, Exist i, a_i -> b_i 사이 아무것도 없고, b_i는 어떠한 a_j -> b_j 사이에도 존재하지 않음(즉 그냥 i를 먼저 밀어버리고 생각 가능)

이 강력한 Claim을 바탕으로 문제를 그냥 풀어버릴 수 있다. 죄수들을 정점으로 하는 그래프를 생각하자.

i, j에 대해, 

a_i와 b_i 사이 a_j가 존재한다면 j -> i (j가 i보다 먼저 시행되어야 함)

a_i와 b_i 사이 b_j가 존재한다면 i -> j (i가 j보다 먼저 시행되어야 함)

이 그래프에 사이클이 존재한다면 불가능하고, 없으면 위상정렬 가능하므로 그 순서대로 시행해주면 가능하다. 

이를 나이브하게 구현하면 풀테스크를 제외하고 모두 맞을 수 있다.

 

Full Task idea) 그래프를 단순화하자.

 

두 가지 아이디어를 사용할 수 있다.

1. HLD + 세그먼트 트리로 간선 줄이기 테크닉을 이용한다.

2. Sparse Table을 이용한다.

2번의 시간복잡도가 log N만큼 더 빠르다. 

2번을 간단히 설명하자면, LCA를 구하듯이 parent에 대한 sparse table을 전처리한 후 LCA 등을 이용해 적절히 잘 처리해주면 된다.

 

 

Sightseeing in Kyoto

 

이동하기 4(BOJ 18796), https://www.acmicpc.net/problem/18796 와 같은 문제이다.

18796번: 이동하기 4

 

초기에 그냥 쭉 오른쪽으로 갔다가 쭉 올라간다고 생각하자. 이후 이 상태에서 조금씩 경로를 변경한다고 생각할 수 있다. 

 

Ai, Bj를 인접한 두 개의 차로 생각하면, 

cost(x, y) = Ax + By라 할 때, 적절히 칸을 색칠하는 문제가 된다. (높이가 단조감소하는 히스토그램이 되도록 칸을 색칠)

 

간단히 풀이를 설명하자면, A[i] >= A[i+1]일 경우 i층에서 절대 멈추지 않는다. (i+1층까지 색칠된다.) 따라서 이 둘을 그냥 합쳐버릴 수 있다.

cost(i, j) = A[i] + Y[i]B[j] 꼴로 표현해주면, A[i] / Y[i] >= A[i+1] / Y[i+1]일 때 A와 Y를 합쳐주면 된다.

이를 어떠한 순서로 합쳐도 convex hull 꼴이 나오므로 동일한 결과가 나오고, B와 X에 대해서도 해주면 된다.

그러면, cost(i, j) = A[i]X[j] + B[j]Y[i] 꼴이 나온다. 

 

이후 합친 것을 다시 분해해 준다. 동일한 A를 가지도록 분해해주면 되는데, convex hull의 선분에 정점을 찍는다고 생각하면 된다. 

이런 처리를 마치면 단조성을 가지므로 cost(i, j) <= 0인 모든 i, j는 높이가 단조감소하는 히스토그램이 되고, 이 히스토그램이 최적해이다. 

 

Misspelling

 

길이 N string S에 대해 T_i를 S에서 i번째 단어를 날려버린 문자열이라 하자.

M개의 쌍 a_i, b_i가 주어지는데, 이는 T_(a_i) <= T_(b_i)임을 의미한다. (사전순)

이를 만족하는 S의 개수를 구하자. (S는 알파벳 소문자 = 26개로 이루어져 있다.)

 

DP[i][k] : a_i != a_(i-1)이고 a_i = k인 가짓수.

DP[i][l]을 구해보자. 

DP[j][k]를 생각해보면,

모든 a, b 쌍에 대해,

a < j or b < j -> j-1 이하에서 다른 것이 존재하므로, 이미 그 아래에서 대소관계가 결정되어 이건 고려할 필요가 없다.

둘 다 i보다 작거나, 둘 다 i보다 크거나 같음 -> 대소관계가 S_i에 의존하지 않아 고려할 필요가 없다.

 

즉, j <= a < i, b >= i인 경우와 그 반대만 고려하면 된다.

j <= a < i <= b인 경우, T_a <= T_b이므로, l <= k이다.

반대인 경우, k <= l이다.

한 쪽이 i 이상이고 한 쪽이 i 이하인 것들을 따로 분류할 수 있다. 이러한 것 중 a <= i인 것들 중 a의 최대를 t1, b <= i인 것들 중 b의 최대를 t2라 하자. wlog t1 <= t2라 하면, 다음이 성립한다.

 

j <= t1일 땐 k = l(DP 정의에 어긋나므로 불가능)

t1 < j <= t2일 땐 k < l인 것만

t2 < j일 땐 l != k인 아무 l이 모두 가능하다.

 

t1, t2는 셋질을 통해 쉽게 구할 수 있고, 이를 알았을 때 DP[i][l]을 구하는 것은 위 3개를 바탕으로 누적합으로 구할 수 있다.

따라서 O(26N + NlogN) 시간에 답을 구할 수 있다.

 

Day 2.

 

Copy and Paste 3

 

문제 :

다음과 같은 시행 A, B, C가 가능하다.

시행 A : 현재 string에 글자 하나를 추가한다. cost는 A이다.

시행 B : 현재 string을 잘라내기(Ctrl X)를 한다. 이제 string은 비어있지만, 클립보드에 string이 저장된다. 비용은 B이다.

시행 C : 가장 최근에 잘라낸, 즉 클립보드 중 제일 최근의 string을 현재 string 끝에 붙인다. 비용은 C이다.

이 시행을 통해 가장 적은 cost로 원하는 string을 만들어야 한다.

 

기본 아이디어 : DP[a][b] : S[a, .. , b-1]를 만드는 데 필요한 비용으로 정의하자.

길이 1일 때부터 N일 때까지 확장해가며 구할 것이다. 

 

시행 A : DP[a][b] = DP[a+1][b] + A, DP[a][b-1] + A ...

시행 B와 C를 처리해주기만 하면 된다.

DP[x][y], y - x = len 이라 하자. 이 x~y를 완성한 후, B 시행 후 여러 번 C를 사용하는 상황을 생각해보자.

string S' = S[x, .. y-1]이라 하자.

이후 이 DP의 전파에서, 시작이 S'인 경우만 전파해주어도 상관이 없다. 이는 위 시행 A에서 DP[a+1][b] + A로 인해 자연스래 전파되기 때문이다.

따라서 그냥 DP[x][y]에 B 시행 후 C를 사용하는 경우에 대해선 D[x][k] (k > y)의 경우에만 해주어도 괜찮다.

이는 마찬가지로, 끝이 S'인 경우만 전파해주어도 상관이 없다. 

즉, 다음과 같은 형태일 때 전파해주면 된다.

[S' .... S'].

또한, S'이 겹친다면 어떻게 해야 할까?

[ S' ] ... [   [  ]   ] -> S'을 복사 - 붙여넣기 할 수 있는 횟수가 최대한 많도록 전파해야만 한다.

다음과 같은 경우를 생각해보면, 뒤쪽에 있는 S'에 붙여넣는 경우는 복붙 횟수가 더 앞에 있는 S'에 붙여넣는 경우보다 낮거나 같다. 즉,

복사-붙여넣기 횟수가 동일하다면 최대한 짧은 스트링에 전파해야 한다. (넓은 것은 시행 A로 인해 자연스래 전파되므로)

이는 그냥 현재 string이 i .. k-1일 때, [k .. n]에 S'이 포함되는 최소 n을 잡는 것을 반복하면 된다. (이는 스위핑으로 자연스럽게 처리된다.)

시간복잡도를 생각해보자. len = 1일 때 NxN, len = 2일 때 NxN/2, ... N x N/len번 도므로, 

sigma 1/i ~ logN이므로, 시간복잡도는 N^2logN이다. 

 

Flights

 

추가 예정

 

Team Contest

 

N명의 학생이 있다. 각 학생은 세 가지의 능력을 가지는데, 각각 X_i, Y_i, Z_i라 하자.

이 중 세 명의 학생을 모아 팀을 만들 것인데, 이 팀은 다음 조건을 만족해야 한다.

 

조건 : 이 팀에 대해 각 학생은 자기들만의 강점이 존재한다. 즉 각 학생들은 하나의 능력에 대해 이 팀의 다른 학생들보다 우위에 있다.

 

이 조건을 만족하는 팀에 대해서, 이 팀의 능력이 가장 최대인 팀을 고르고자 한다. 팀의 능력은 각각의 능력에 대해 세 명의 최대로 정의되며, 이 세 가지 능력의 합이 팀의 능력이다. 팀의 능력의 최대를 구해보자.

 

먼저, 만약 각 능력에서 최대인 능력을 가진 사람이 있을 것이다. 

만약 이 사람이 모두 다르다면, 이 세명이 답이다.

만약 모두 같다면, 이 사람이 포함된 팀은 무조건 상위호환이 존재하는 학생이 있다. 따라서 이 사람은 팀에 포함될 수 없다.

 

다음과 같은 알고리즘을 통해 답을 얻어냈다.

각 능력에 대해 priority queue를 관리하자.

1번 능력에 대해 가능한 후보군을 a, 2에 대해 b, 3에 대해 c라 하자.

 

만약 a의 1번 능력이 b의 1번 능력보다 낮거나 같았다고 하자. 이 경우, b는 2번 능력 강점을 가진 참가자로써 이 팀에 절대 들어올 수 없다. 이는 b가 이미 2번 능력에 강점을 가지고 있음에도 불구하고 1번 능력의 남은 후보군 중 1번 능력이 가장 큰 a보다 1번 능력이 크거나 같으므로 두 개 이상의 능력에 대해 팀 내에서 최대가 되기 때문이다. 

이 경우, b를 2번 능력 최대 후보군에서 제외하고 다음 후보군 중 2번 능력이 최대인 것을 뽑는다. (PQ 이용)

 

이를 반복하면 된다. 만약 a, b, c에 대해 조건을 만족한다면 그것이 바로 답이고, 이러한 것이 존재하지 않는다면 답이 존재하지 않는다.

 

 

Day 3

 

 

Broken Device 2

 

Sprinkler

 

Ants and Sugar

 

 

Day 4

 

Super Dango Maker

 

0827 Problem Solving을 참고하라.

 

Fish 2

 

 

Reconstruction Project

 

0903 Problem Solving을 참고하라.