0907 ~ 0908

어제 오늘 이틀동안 푼 문제에 대한 정리.

코드포스 201라운드쯤부터 Div2 D~E~F? 를 푸는 연습을 시작했다. 꾸준히 할 수 있을진 모르겠지만 하루에 한 문제라도 푸는 걸 목표로.

아래는 어제~오늘 아침까지 푼 문제들 코멘트.

201D. Lucky Common Subsequence

두 문자열 a,b와 바이러스 문자열 v가 주어졌을 때, v를 substring으로 포함하지 않는 문자열 a,b의 LCS(longest common subsequence)를 구하는 문제다. 세 문자열 길이가 모두 100밖에 되지 않아 단순 DP로 풀기 쉽고, 푸는 과정에서 바이러스 문자열 v를 얼마나 포함하고 있는지를 갱신해주기 위해 KMP 알고리즘의 응용이 필요하다. 문제 자체는 좀 전형적이었는데 KMP 짜는게 잘 기억이 안 나서 애먹었다.

풀고 201E는 옛날에 풀었어서 202 라운드로 넘어갔다.

202D. Apple Tree

n개의 정점을 가진 트리가 있다. 트리의 리프 노드에는 0 이상의 숫자가 적혀 있고 나머지 노드는 0이 적혀있다. 어떤 트리 k의 무게를 그 트리의 서브 트리에 적힌 모든 숫자의 합으로 정의하자.

또, 어떤 트리에 대해 그 트리의 모든 자식들이 같은 무게를 가지고 있을 때 그 트리가 '균형 잡혀있다'라고 말한다. 트리의 모든 정점 v에 대해 그 정점 v의 서브트리가 균형잡힌 트리가 되게 하기 위해 감소시켜야하는 숫자의 최소치를 계산하는게 문제이다.

dfs의 적절한 응용으로 풀리는 문제고, 풀이는 비교적 빨리 생각했는데 예외를 제대로 처리하지 못해서 좀 시간이 오래걸렸다. leaf 노드에서부터 차근차근 위로 올라오면서 한 번에 감소시킬 수 있는 숫자의 최소 단위를 계산하고, 현재 값에서 감소시키는게 아니라 0에서 시작해서 현재 숫자이하의 가능한 최댓값을 만드는 식으로 접근하면 풀기가 훨씬 쉽다. unit 단위가 0이 되거나 너무 커져버리거나 하는 경우에 대한 예외를 제대로 다루지 못해서 몇 번 틀렸다.

202E. Subset Sums

n(<=10^5)개의 숫자로 구성된 집합과 그 집합의 부분 집합이 m(<=10^5)개 있다. 부분 집합의 모든 원소 개수 합은 항상 10^5개 이하인게 보장된다.  이 때 아래의 q개 쿼리를 수행한다.

1. ? k : k번째 부분 집합의 모든 원소 합을 출력한다.

2. + k x : k번째 부분 집합의 모든 원소에 각각 x를 더해준다. 이 때 이 덧셈은 이 부분 집합 뿐만 아니라 이 부분 집합과 같은 원소를 포함하고 있는 다른 모든 부분집합에도 영향을 끼친다.

이 문제는 좀 고민하다가 도저히 풀이가 떠오르지 않아서 풀이를 봤다. 풀이를 보니 아마 절대 못 풀었을 것 같은데.. sqrt decomposition의 개념이 이런 식으로도 쓰일 수 있다는게 너무 놀라웠다. 정말 많이 배운 문제.

풀이는 m개의 부분 집합 원소 개수 합이 10^5개를 넘지 않는다는 성질을 이용한다. 부분 집합 중에 원소 개수가 sqrt(n)개 이하인 것을 light set, sqrt(n)개 이상인 것을 heavy set이라고 하면, 조건 상 heavy set의 개수는 sqrt(n)개를 넘지 않는다.

이를 이용해서, 미리 전처리로 각각의 부분집합에 대해 heavy set과 서로 겹치는 원소의 개수를 계산해두고, 쿼리에서 경우의 수를 4개로 나눠서(light set 합 계산, light set에 덧셈, heavy set 합 계산, heavy set에 덧셈), 각 경우가 모두 최악의 경우에도 sqrt(n) 시간 안에 동작하게 만든다. 이 방식이 굉장히 신기했고 재밌는 문제였다.

그리고 밤에 참가했던 대회에 대한 정리. Educational Codeforces Round50에 참가했다.

아직 시스템 테스트가 안 끝나서 틀릴 수도 있지만 일단 정리.

A. Function Height

지문은 길고 복잡한데 그냥 간단한 계산식 출력하면 되는 문제였다. 지문 읽는데 2분, 코드 짜는데 10초였던 듯

B. Diagonal Walking v.2

(0,0) -> (n,m) 까지 8방향으로 걸어서 k번 안에 도착 가능한지, 그리고 도착 가능하다면 이 때 가능한 최대 대각선 방향 이동 횟수를 묻는 문제이다. 나는 별로 어렵지 않다고 생각하고  풀었는데 생각보다 이 문제에서 말린 사람이 많았다.

x,y축을 별도로 생각해서 각각 0칸 움직이는 횟수를 최소로 하는 방법을 떠올리면 그 두가지를 합치는 것은 어렵지 않다.

C. Classy Numbers

l~r 까지 구간에 대해 0이 아닌 숫자가 3개 이하로 나오는 수의 개수를 구하는 문제이다. 1 ~ x까지 그러한 숫자의 개수를 세는 함수를 count(x)라고 하면 count(r) - count(l-1)을 계산하면 돼서 이런 형태로 바꾸어서 풀었다. 각 개수를 계산하기 위해 좀 복잡한 방법을 썼는데 나중에 알고 보니 이러한 숫자의 개수 자체가 많지 않아서 모든 수를 다 구한다음 lower_bound, upper_bound를 써도 된다는 것을 알았다. 

백준에서 비슷한(+좀 더 어려운) 유형을 여러 번 접해서 그런지 문제를 생각도 안하고 어렵게 접근한 것 같아서 좀 아쉽다. 빨리 풀긴 했지만...

D. Vasya And Arrays

두 개의 배열이 주어진다. 각 배열은 연속한 원소들을 그 원소의 합인 하나의 원소로 줄일 수 있다. 이 때, 두 배열을 같게 만들 수 있는지, 그리고 같게 만들 수 있다면 가능한 배열의 최대 길이는 얼마인지 묻는 문제였다.

문제가 D 치고 너무 쉬웠는데, 그냥 배열의 prefix sum 배열에서 겹치는 원소 개수가 몇 개인지 물어보는 문제로 환원할 수 있다. 배열 전체 합이 일치하지않으면 불가능, 일치하면 겹치는 원소 개수 출력. 

E. Covered Points

양 끝점이 정수인 n(<=1000)개의 직선이 주어진다. 이 때, 각 직선은 겹치지 않는다(최대 한 점에서만 만난다). 이 때 직선 위에 존재하는 좌표가 정수인 점의 개수를 구하는 문제.

문제는 단순했고 풀이도 단순했다. 그냥 직선 별로 그 직선 위의 정수 좌표 개수를 세 준다음 N^2 루프를 돌면서 정수인 교점이 있는지 보고 있다면 그 교점을 제거해주면 되는 문제.

직선 별로 정수 좌표 개수는 dx, dy를 구한다음 dx와 dy의 최대공약수 g에 대해 1 + g니까 그냥 그걸 더해주면 되고, 교점 계산은 교점 좌표 구하는 공식을 이용해서 계산 한다음 분모 분자가 서로 나누어 떨어져야 정수 좌표이므로 이 조건을 고려해주면 이 것도 그렇게 어렵지 않다.

근데 같은 점을 두 번 제거하게 되는 예외가 있어서 이걸 처리해줘야 하는데, y축에 평행한 직선을 생각을 안하고 겹치는 점 처리를 x좌표 하나만 가지고 해줬다가 그 예외를 대회 끝날 때까지 못 떠올리고 틀렸다 ㅠㅠ 기하에 너무 약한 것 같다. 기하 공부를 좀 해야한다는 생각이 들었다.