KimHwon

난이도가 좀 괴상하다. B1+B2 푼 사람보다 C푼 사람이 더 많다.

꾸역꾸역 B2를 밀었더니 Codeforces Anytime에서 오렌지 퍼포먼스가 떴다 ㅋㅋ

A. Common Prefixes

인접한 두 문자열의 공통 prefix의 갯수가 주어질 때, 만족하는 문자열의 배열을 출력하는 문제. 각 문자열의 한 문자에 대해서 생각해보면, 서로 같은지 다른지만 중요하는 것을 알 수 있다. 따라서 모든 문자를 a와 b로 통일해보자. prefix 갯수만큼은 그대로 두고, 그 이후는 이전 문자열과 다르게 선택하면 된다. 문자열의 길이에 대한 조건이 있는데, 이미 조건을 만족했으므로 그냥 최대 길이인 200개로 꽉 채워서 만들어도 된다.

B2. Koa and the Beach

시간에 따른 파도를 { k, k-1, k-2, ... , 2, 1, 0, 1, 2, ... , k-2, k-1, k } 로 변환해보자. 그러면 각 위치에서 존재할 수 있는 시간이 구간으로 나타나게 된다. 시간이 지남에 따라 현재 높이를 잘 관리하면, 현재 높이가 구간 안에 들어가 있는지 확인해줄 수 있다. 만약 모든 구간이 가능한 경우 즉, 시간과 무관하게 항상 가능한 위치가 있다면 원하는 높이로 이동할 수 있다.
현재 높이가 구간 왼쪽에 있다면, 조금 더 기다려서 높이가 낮아지기를 기다릴 수 있다. 반대로 구간 오른쪽에 있다면 더 이상 진행할 수도 없고 기다릴 수도 없기 때문에 실패한다. 이 과정을 시뮬레이션하면 O(n)안에 해결이 가능하므로, 두 문제 모두 해결이 가능하다.

딱봐도 더러워보이는 문제다. 버추얼이라 그냥 망할 각오하고 구현했더니 다행히 맞았다. 레이티드였으면 나도 C로 도망갔을 것 같다.

C. String Transformation 1

제일 먼저, 더 작은 문자로는 변경할 수 없으므로 모든 문자를 순회하면서 예외처리해준다.
각 문자를 변경하는 과정을 그래프로 모델링해보자. 어떤 문자 X를 Y로 바꾸는 것을 정점 X에서 Y로의 간선으로 표현할 수 있다. 잘 관찰해보면 간선의 방향이 더 큰 문자 방향으로만 생기므로, 이 그래프는 DAG임을 알 수 있다. 즉, DAG에서 최소 갯수의 간선을 사용해서 모든 정점을 지나는 방법에 대한 문제가 된다. 그래프에서 모든 정점이 연결되면서 간선의 갯수가 최소인 경우는 spanning tree임이 자명하다. 트리의 간선의 갯수는 (연결된 정점의 갯수)-1 이므로 union-find 등으로 그래프의 연결 상태를 세어주고 간선의 갯수를 계산하면 된다. 그래프들이 서로 연결되지 않을 수도 있음에 주의하여, 각 컴포넌트끼리 따로 계산해준다.

약간 짬밥?으로 풀었다. 아이디어가 없어서 말린 문제들 중에 그래프로 모델링하는 풀이가 많았어서, 뭔가 상태 전이가 있는데 아이디어가 전혀 떠오르지 않으면 그래프로 한번 모델링해보는 경향이 있다. 모델링해보니까 금방 규칙이 보였다.

딥3라 언레. 너무 급하게 풀어서 그런지 B번에서 뇌절을 심하게 했다.

A. Spy Detected!

map을 사용해 등장한 숫자의 개수를 세고, 1개인 원소의 위치를 출력함.

B. Almost Rectangle

두 점의 위치를 각각 (x1, y1), (x2, y2)라고 하면, 조건을 만족하는 위치들은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이다.
그런데 만약 x1과 x2가 같거나 y1과 y2가 같으면 직사각형 모양이 나오지 않기 때문에 x'을 임의로 x1+1 또는 x1-1로 정할 수 있다. 둘 중에 가능한 것 하나를 골라서 새로운 위치로 지정한다. 마찬가지로 y에 대해서도 y'을 잘 정한다.
쉬운 문제였지만 x' 또는 y'이 가능한지 확인을 제대로 하지 못해서 두 번이나 틀렸다. 너무 긴장해서 급하게 제출했던 것 같다.

C. A-B Palindrome

constructive하게 해결이 가능하다. 수열에서 0의 갯수와 1의 갯수가 주어지므로(각각 a와 b), 입력된 수열에서 이미 정해진 숫자만큼 미리 센다. 만약에 a나 b가 음수가 되면 더 볼 것도 없이 불가능한 상태이다.
수열을 한 번 순회하면서 S[i] == S[N-1-i]를 만족하도록 ?를 가능한대로 채워 넣는다. 동시에 a와 b를 소모하면서 음수가 되지 않는지 확인한다. 이렇게 하여 먼저 자명한 숫자들에 대해서 팰린드롬을 만족하게 할 수 있다.
남는 ?들에는 숫자를 가능한대로 채워 넣는다. 다 채웠을 때 a나 b가 음수가 되면 불가능한 상태임을 알 수 있다.

D. Corrupted Array

먼저 미리 주어진 수열의 합을 구해둔다. 그 후 주어진 수열 b를 순회하면서 b에서 제외할 숫자 x를 정한다. 수열의 총 합에서 x를 뺀 값은, a의 각 원소들과 a의 모든 원소의 합이다. 다시 말해서 (a의 합)*2이라는 뜻이다. 이를 2로 나눈 뒤 (나눠지지 않으면 예외처리한다.) 그 값이 b에 존재하는지 set등을 사용해 확인한다.

E. Permutation by Sum

구간 [L, R]에 대해서 가장 작은 경우는 [1, 2, ... , L-R+1]이고 가장 큰 경우는 [N, N-1, ... , N-(L-R+1)]이다. S가 가장 작은 경우랑 큰 경우 바깥이면 불가능하다. 반대로 가장 작은 경우랑 큰 경우 안쪽에선 S를 만족하는 수열이 항상 존재한다.
만약 가장 작은 경우에 모든 원소에 1씩 더해준다고 하면, 구간합이 L-R+1씩 증가한다. 그런데 구간의 길이가 L-R+1이므로 한 원소씩 더해주면 사이에 모든 공간이 채워진다.
큰 원소부터 하나씩 더해나가면 구간 [L, R]의 합이 S면서 항상 서로 겹치지 않는 수들의 집합으로 만들 수 있다. [L, R]을 잘 구성하고 남은 위치들에 아직 사용되지 않은 수를 적절히 채워 넣으면 된다.

F. Education (업솔빙)

각 위치에서 가진 돈을 일차함수로 그려보면 CHT 처럼 나타난다. O(n)으로 시뮬레이션하면서, 현재 일차식과 다른 일차식을 비교해서 목표하는 돈을 먼저 모으는 쪽으로 계속 업데이트해 나가면 된다.

C번에서 엄청 말렸다. 결과는 똑떨.  아슬아슬하게 1600점 파킹했다.

학기 시작하고 PS를 자주 못하니 실력이 떨어지는게 눈에 보이기 시작했다.

A. Déjà Vu

처음 주어진 문자열이 팰린드롬이라면 정가운데를 제외하고 어디에 넣든지 팰린드롬이 아니게 된다. 주어진 문자열이 팰린드롬이 아닌데 a를 넣어 팰린드롬이 되는 경우를 생각해보면, 만약 맨 뒤에 a를 추가해 팰린드롬이 되었다면 반대로 맨 앞에 a를 추가한 경우는 전자를 왼쪽 쉬프트한 문자열이고 반대도 마찬가지다. 따라서 둘 중 하나는 무조건 팰린드롬이 아니게 된다. 따라서 처음 주어진 문자열의 맨 앞 또는 맨 뒤에 a를 추가해보고 둘 다 팰린드롬이 나오는 경우만 제외한 모든 경우가 불가능하다.

B. Flip the Bits

주어진 문자열을 반전시킬 수 있는 조건은 그 부분수열의 0의 개수와 1의 개수가 같아야 한다. 그런데 0과 1의 개수가 같으므로 반전시킨다고 해도 같다는 것이 보장되며, 처음 상태에서 0과 1의 개수가 같기만 하면 얼마든지 연산을 적용해도 성립함을 알 수 있다. 따라서 주어진 문자열을 뒤에서부터 확인하면서 두 문자열이 같아지도록 마음대로 뒤집으면 된다. 반전하지 못하는 경우가 생기면 실패이고, 아니면 성공이다. 뒤집어진 상태를 boolean 으로 플래그를 정해서 관리하면 편리하다.

C. Balance the Bits

일단 괄호 문자열의 시작점은 여는 괄호, 끝점은 닫는 괄호임이 자명하다. 따라서 두 괄호문자열의 시작점과 끝점은 동일해야 하므로 둘다 1로 표시되어야 한다. 또한 첫 번째 괄호 문자열이 성립한다고 가정했을 때 두 번째 괄호 문자열도 성립하려면, 첫 번째 괄호 문자열에서 짝수 개의 괄호가 바뀌어야 한다. 따라서 주어진 수열에 1과 0이 모두 짝수 개 등장해야 한다. 이 조건을 만족하면 모두 성립한다.

괄호 문자열을 construct하는 방법은, 첫 번째 괄호 문자열을 ()()()... 이런 식으로 정한다. 두 번째 괄호 문자열은 첫 번째에 맞춰서 정한다. 두 개씩 끊어서 하나로 보고, 두 번째 문자열이 성립하지 않으면 반전시키고 첫 번째 문자열도 함께 반전시킨다. 이렇게 되면 첫 번째 괄호 문자열은 () 또는 )(로만 이루어지는데 이는 항상 성립하는 형태이다.

Expert라 언레다. 푼 사람 수를 보면 F,G도 풀었어야하는데 좀 아쉽다.

A. Strange Table

n x m 행렬 A에서 A_ij 를 알 때, A_ji를 구하는 문제. 행과 열을 나눈 몫과 나머지를 다시 조합해서 해결.

B. Partial Replacement

주어진 문자열에서 정해진 위치만 x로 바꿀 수 있다. 최소한으로 바꿔서 각 x들 사이 거리가 k 미만이 되도록 하는 문제. 왼쪽 끝과 오른쪽 끝은 문제에서 무조건 바꾸라고 하였으니 그대로 바꾼다. 양 끝의 바뀐 x들 사이를 순회하면서, 길이가 k 이상이 되는 지점 직전을 교체해 나간다. 왼쪽 끝과 오른쪽 끝 사이 길이는 고정이니, 어떻게 바꾸던지 (r-l+1)/k 개 교환됨은 자명하다.

C. Double-ended Strings

문자열의 맨 앞 글자 또는 맨 뒷 글자를 제거할 수 있다. 최소한으로 제거하여 두 문자열이 일치하게 만드는 문제. 두 문자열의 길이가 20으로 매우 짧으므로, 첫 번째 문자열의 모든 substring, 두 번째 문자열의 모든 substring을 비교할 수 있다. 가능한 긴 공통 substring을 찾으면 된다.

D. Epic Transformation

주어진 수열에서 서로 다른 임의의 두 원소를 고르고, 고른 둘을 없앨 수 있다. 만들 수 있는 수열의 최소 크기를 구하는 문제. 해석해보면 www.acmicpc.net/problem/19590 이 문제와 일치한다. 즉, 수열에서 가장 많은 원소가 절반 이하면 무조건 가능하고, 절반 이상이면 절반을 넘는 만큼 남는다.

E. Restoring the Permutation

주어진 수열에서 원소의 값이 바뀌었다는 것은 원본 수열의 해당 위치가 새로운 최댓값이라는 뜻이며, 그렇지 않다는 것은 원본 수열의 해당 위치에 현재 최대값 이하의 원소가 있다는 뜻이다. 수열의 값이 바뀌는 지점에서는 원본 수열의 값이 자명하므로 고정하고, 남은 위치들을 조건에 맞게 적절히 채워 나가면 된다. 최소 수열을 만드려면, 가능한 작은 값을 앞에서부터 채워 나가면 된다. 한편, 최대 수열의 경우는 가능한 큰 값을 앞에서부터 채워 나가야 하는데 현재 최댓값 이하의 원소가 있어야 하므로, set을 사용해 upper_bound-1 값으로 채워 나가면 된다.

A. Strange Partition

수열과 정수 x가 주어진다. 수열의 원소들을 적절히 서로 합쳐서, 각 원소를 x로 나누고 올림한 값들의 총합이 최소가 되거나 최대가 되게 해야하는 문제.

어떤 수를 x로 나누고 올림했을 때 값이 바뀌려면 x로 나눈 나머지가 있어야 한다. 잘 생각해 보면 두 원소가 따로 있을 때는 x의 배수가 아니다가 합치면 x의 배수가 되어버릴 수 있다. 그러면 합치기 전에는 각각 올림해서 값이 증가할 텐데, 합친 뒤에는 나머지가 없기에 올림을 해도 값이 증가하지 않는다. 따라서 모든 원소를 다 합쳐버린 상태가 최소가 되는 상태이고, 전혀 합치지 않은 상태가 최대가 되는 상태이다.

B. Strange List

수열과 정수 x가 주어진다. 수열을 하나씩 순회하면서 지금 보는 원소가 x로 나누어지면, 그 몫을 x개 만큼 수열 맨 뒤에 추가한다. 만약 x로 나누어지지 않으면 끝낸다. 끝난 시점에서 수열의 총 합이 얼마인지 알아내는 문제.

일단 원소를 나눈 몫을 x개 추가하므로, 새로 추가되는 수들의 합은 원래 원소의 값과 같다. 즉, a_i/x를 x개 추가하므로 a_i/x * x = a_i 인 것이다. 새로 수열에 추가되는 연산이 최대 몇 번 있는지 생각해보면, 어떤 원소가 같은 수로 계속 나누어 떨어져야 한다. 입력되는 범위(<=10^9) 내에서 이런 경우는 2^29을 2로 나누는 경우일 것이다. 최대 29번 나누어지므로 각 원소당 29번 이내에 반복이 끝난다는 것을 알 수 있다. 따라서 그냥 주어진 수열에 끝나는 조건이 나올 때까지 x로 나눠나가다 보면 된다.

C. Strange Birthday Party

수열 k와 정렬된 수열 c가 주어진다. k의 모든 원소에 대하여 1. j<=k_i 를 만족하는 c_j 를 더하거나 2. c_{k_i}를 더할 수 있다. 단, 1번 방법에서는 c의 원소를 한 번씩만 사용할 수 있다. 합을 최소화하는 문제.

c가 정렬되어 있으므로 k_i가 클 수록 2번 방법을 선택했을 때의 페널티가 커진다. 따라서 k_i가 클 수록 가능한 1번 방법을 선택하는 것이 최적이라고 생각해 볼 수 있다. k를 내림차순으로 정렬하고, c_{k_i}의 합을 관리한다. 가장 큰 k_i부터 1번 방법으로 가장 작은 c_j를 선택해나가 보자. 적절히 합을 관리한다면 모든 경우를 확인할 수 있다.

D. Strange Definition (업솔빙)

두 수 x와 y에 대하여 lcm(x,y) / gcd(x,y) 가 완전제곱수면 '인접'했다고 정의해보자. 수열이 하나 주어지고 1초가 지날 때마다 서로 '인접'한 원소들이 서로 곱해진다. 쿼리로 시간이 주어졌을 때 각 쿼리에서 '인접'한 원소가 가장 많은 수를 알아내는 문제.

서로 '인접'한 원소들을 관리해주는 것이 키포인트이다. 어떤 원소를 소인수분해하면 a^3 * b^4 * c^5 이런 식으로 나올텐데 홀수 차수인 값만 남기고 무시해도 된다. 즉, a * c 이렇게 두 인자만 남게 된다. 왜냐하면 제곱수는 lcm(x,y) / gcd(x,y)한 후에 남아있어도 인접한 것은 자명하기 때문이다. 0초에서 1초로 넘어갈 때는 서로 곱해질 텐데, 이 경우도 마찬가지로 짝수차수가 만들어지면 무시하고 홀수 차수인 값만 남길 수 있다. 이렇게 되면 이전 상태에서 그대로 있거나 1로 바뀌게 된다. 1초에서 2초로 넘어갈 때는 이미 1초로 넘어올 때 정리가 되었기 때문에 '인접'한 관계가 변하지 않는다. 즉, 0초일 때 한번, 1초일 때 한번만 '인접'한 원소들의 수를 세어주면 된다.