Codeforces Round #805 (Div. 3)

A. Round Down the Price

code

문제 설명

숫자 \( n\)이 주어진다. \(n\)이하의 \(10^k\)꼴 (\(k\)는 음이 아닌 정수)인 수 중 가장 큰 수를 구한 뒤 \(n-10^k\)를 출력하는 문제이다

알고리즘

단순 구현 문제이다. 반복문을 이용하여 \(n\)이 넘을 때까지 1에서 10씩 곱해나가고, \(n\)을 넘기면 10으로 나눈다. 이 수가 \(n\) 이하의 수 중 최대인 \(10^k\)꼴의 수이다.

B. Polycarp Writes a String from Memory

code

문제 설명

하루에 최대 3종류의 글자만 적을 수 있다. 문자열 \(s\)가 주어지고 맨 앞글자부터 마지막 글자까지 순서대로 적을 때, \(s\)를 적기 위해 최대 며칠이 걸리는 지 출력해야 한다.

알고리즘

단순 구현 문제이다. 맨 앞글자부터 지금까지 몇 종류의 글자가 나왔는지 세고,  만약 3종류를 넘었다면 답을 1 증가시키고 종류를 초기화한 뒤 다시 센다.

C. Train and Queries

code

문제 설명

기차가 \(n\)개의 정거장을 순서대로 지난다. \(i\)번째에는 \(u_i\)번 정거장을 지난다.

\(q\)개의 쿼리가 주어진다. 각 쿼리는 \(a, b\)로 이루어져 있으며, 기차를 타고 \(a\)번 정거장에서 \(b\)번 정거장까지 갈 수 있는지 여부를 출력해야 한다.

알고리즘

먼저 \(u_i\)의 범위가 최대 \(10^9\)이기 때문에 좌표 압축을 이용하여 정거장 번호가 최대 \(n\)이하가 되도록 하였다.

이후, 모든 정거장에 대해 \(i\)번 정거장에 가장 빨리 도달하는 시점을 \(\min[i]\), \(i\)번 정거장에 가장 늦게 도달하는 시점을 \(\max[i]\)라 하자.

그렇다면 각 쿼리 \(a, b\)는 먼저 기차가 \(a\)와 \(b\)번 정거장을 지나는 지 확인하고 \(\min[a] \le \max[b]\)를 만족하는 지 확인하면 된다.

D. Not a Cheap String

code

문제 설명

문자열 \(s\)가 주어진다. 문자열의 비용은 각 알파벳 순서(1이상 26이하)의 합이다. 여기서 최소한의 개수의 문자를 지워 이 문자열의 비용이 \(p\) 이하가 되도록 하려고 한다. 문자를 지운 후 \(p\)이하의 비용이 된 문자열을 출력해야 한다.

알고리즘

먼저 문자열의 각 문자를 (알파벳, 번호)로 묶은 뒤, 알파벳이 커지는 순으로 정렬한다.

그 뒤 문자열 \(s\)의 비용을 먼저 구한 뒤, 정렬한 결과에서 첫 번째 알파벳부터 차례대로 제거한다.

제거할 때, 실제로 제거하는 것이 아니라 해당 알파벳을 제거한다고 bitset에 체크만 한다.

비용이 p 이하가 되면, bitset에 체크되지 않은 문자만 출력하면 된다.

E. Split Into Two Sets

code

문제 설명

총 \(n\)개의 도미노가 주어지고, 도미노에는 1이상 \(n\) 이하의 수가 2개 적혀있다. 이 \(n\)개의 도미노를 두 묶음으로 나눠 각 묶음에 중복되는 숫자가 없도록 나눌 수 있는지 확인해야 한다.

알고리즘

먼저 각 도미노를 하나의 정점으로 취급하고, 같은 숫자가 적혀있는 도미노는 간선으로 연결한다.이렇게 만든 그래프가 이분 그래프라면 중복되는 숫자가 없도록 나눌 수 있는 것이고, 이분 그래프가 아니라면 나눌 수 없는 것이다.이분 그래프를 만들기 전에 예외 처리를 위해 한 도미노에 같은 숫자가 있는지, 그리고 도미노에 적힌 각 숫자의 빈도가 2인지 확인하였다.

F. Equate Multisets

code

 

문제 설명

각각 숫자 \(n\)개가 적힌 멀티셋 \(a, b\)가 주어진다.

\(a\)에서 임의의 원소를 뽑아 2를 곱하거나 2를 나눌 수 있다. (나머지는 버린다.)

\(a\)에서 위의 연산을 여러 번(0번도 가능하다.) 하여 \(b\)로 만들 수 있는지 확인해야 한다.

알고리즘

먼저 \(b\)의 각 원소에 대해 2의 배수면 2로 계속 나누어 만든 멀티셋을 \(b'\)이라 하자. 만약 \(a\)를 \(b\)로 만들 수 있다면 \(b'\)으로 만들 수 있고, \(a\)를 \(b`\)으로 만들 수 있다면 \(b\)로도 만들 수 있다. 따라서 \(a\)를 \(b'\)으로 만들 수 있는지만 확인하면 된다. \(b'\)은 \(a\)에 있는 수에서 나누기만을 실행해서 만들 수 있어야 한다. 따라서 곱하기 연산은 고려하지 않고, 나누기 연산만 고려해주면 된다.

 

만약 \(b'\)에 2, 5가 있고, a에 10이 있다고 하자. 10을 한 번 2로 나누면 5가 되고, 두 번 나누면 2가 된다. 이런 경우에는 10을 5로 만드는 것이 항상 이득이다.

만약 10을 2로 만든다면, \(a\)에 5로 만들 수 있는 다른 원소가 없다면 \(a\)로 \(b'\)을 만들 수 없다. 하지만 10을 5로 만들고, 만약 \(a\)의 다른 원소를 \(5\)로 만들 수 있다 하더라도 이 원소를 5로 만들고 다시 2로 나누면 마찬가지로 2로 만들 수 있으므로, \(b'\)을 만들 수 있다. 따라서 \(a\)의 각 원소에 대해 최소한으로 나눠 \(b'\)에 있는 수를 만드는 것이 최적이다. 이를 이용하여 아래와 같은 그리디 알고리즘을 설계할 수 있다.

 

1. 먼저 우선순위 큐에 \(a\)의 모든 원소를 넣는다.

2. 우선순위 큐에서 가장 큰 원소 \(x\)를 뺀다.

3.1. 만약 \(x\)가 \(b'\)에 있다면 \(b'\)에서 해당 원소를 제거한다.

3.2. 만약 \(x\)가 \(b'\)에 없다면 우선순위 큐에 \(\frac{x}{2}\)를 넣는다.

3.3. 만약 \(x\)가 0이 된다면, 해당 원소는 \(b'\)에 있는 원소로 만들 수 없다는 의미이므로 답이 No가 된다.

4. \(b'\)의 모든 원소가 제거될 때까지 2와 3을 반복한다.

G2. Passable Paths (hard version)

code

문제 설명

정점이 \(n\)개인 트리와 \(q\)개의 쿼리가 주어진다. 각 쿼리는 \(k\)개의 정점으로 이루어져 있다.

이 \(k\)개의 정점이 한 경로위에 있는지 여부를 출력해야 한다.

알고리즘

sparse table을 활용한 lca를 이용하여 해결할 수 있다.

먼저 각 쿼리에 대해 \(k\)개의 정점의 lca를 구하고 이를 \(LCA\)라 하자. 만약 이 \(k\)개의 정점이 한 경로위에 있으려면, \(k\)개의 정점 중 2개 이하의 정점 \(p1\)과 \(p2\)를 잘 고르면 \(k\)개의 정점이 모두 \(p1\)과 \(LCA\)까지의 경로 위, 또는 \(p2\)와 \(LCA\)까지의 경로 위에 있어야 한다. 이러한 \(p1\), \(p2\)가 존재하면 주어진 \(k\)개의 정점이 한 경로위에 있는 것이다.

먼저 트리의 root을 1로 잡은 뒤 각 정점의 높이를 계산해둔다. (root에서 멀어질수록 높이 값은 커진다.)

이제 각 쿼리를 처리하기 위해 \(p1\), \(p2\)를 계산해야 한다.

먼저 \(LCA\)를 구하고, \(k\)개의 정점을 높이 값이 큰 정점부터 작은 정점 순으로 정렬한 뒤 이 순서대로 \(p1\), \(p2\)를 결정한다.

\(p1\)은 맨 앞에 있는 점으로 선택한다. \(p2\)는 정렬된 순서로 정점을 보면서 \(p1\)과 \(LCA\) 있는 정점이 아닌 점으로 선택한다.

이제 \(p1\)과 \(p2\)가 위에서 서술한 조건을 만족하는 지 확인해주면 된다.