PS 일지 (4/19 ~ 5/5)

오랜만에 AGC + 랭작을 했다.

 

AGC066

A. 체스보드 컬러링 후 mod 2d 기준 0/d로 맞추면 된다.

B. 못 풀겠어서 풀이를 봤다. 5^i는 2를 곱할 때마다 자릿수 합이 감소하는 경향을 보인다. 적당히 5의 거듭제곱을 많이 이어 붙여서 노이즈를 제거하자.

C. 못 풀겠어서 풀이를 봤다. 제거 가능할 필요충분조건은 A가 B의 2배면서 왼쪽이나 오른쪽 끝에 B가 있는 경우다. 이를 이용하면 dp를 할 수 있다.

D. 몇 개의 점은 고정하고 그 주변에 있는 A를 퍼뜨린다는 느낌으로 해를 표현할 수 있다. 각 점을 고정했을 때 영향을 받는 구간을 모두 구한 후 dp를 돌리면 된다.

E. BOJ 18873이랑 같다. 돌의 배치를 고정해두고 swap 가능한 두 점을 모두 찾아보자. 부모가 자식과 swap 가능할 조건은 돌 개수에 대한 식으로 표현이 가능하고, 형제끼리는 항상 swap이 가능하다. K를 점점 줄이면서 컴포넌트를 합치면 문제를 풀 수 있다.

F. 못 풀겠어서 풀이를 봤다. 일단 ABC로 이루어진 문자를 A+--+과 같이 mod 3 기준 +인지 -인지로 바꿔서 생각하면 편하다. 시행은 대충 +++을 ---로 바꾸거나 그 반대의 형태라는 것을 알 수 있다. 이때, +++/---를 최대한 제거해서 만든 문자열은 유일하고, 이렇게 얻은 문자열이 일치할 때만 s->t 또는 t->s가 가능하다. 맨 앞이랑 맨뒤에 시행할 경우 예외가 발생하기 때문에 케이스워크를 좀 많이 해야 한다. 에디토리얼에 모든 케이스가 잘 나와있다.

 

BOJ 18789 (814-2)

모든 네자리수를 만든다는 마인드로 접근해야 편하다. 네 자릿수 종류를 점수로 하고 DLAS(https://gist.github.com/cgiosy/ed16f4988eeb7e989a97644fe61e1561)라는 걸 적용해서 풀었다. 예전에 9900점대 해를 몇 개 구하고 접었는데 이번에 학교 서버의 도움을 받아 10000점대 해를 추가로 구했다.

 

BOJ 25313 (Race for the Galaxy)

LGV lemma라는걸 적당히 적용하면 det(Ax+B) 같은 걸 계산해서 문제를 풀 수 있다. 인터폴레이션 하면 네제곱이라 너무 느리고 특성다항식을 써서 열심히 하면 세제곱에 계산할 수 있다.

 

BOJ 21265 (Ascending Matrix)

25313이랑 풀이 방식이 똑같다. 모델링이 좀 더 어렵고 재밌다.

 

BOJ 21117 (Number of Colorful Matchings)

mod 2라서 sign을 고려할 필요가 없다. 그래서 걍 det(Ax+B)를 구하면 된다.

 

BOJ 15943 (parentheses recover)

t가 주어졌을 때 가능판별하는 문제와 비슷한 상황의 문제를 출제한 적이 있다. (https://www.acmicpc.net/problem/27085)

17694(Sparklers), 9539(Escape)도 꽤 비슷한 문제다.

'('를 +1, ')'를 -1로 놓고 s의 누적합을 계산하자. (흔히 이를 "산"이라고 부른다.) 누적합이 최대인 지점, 즉 산꼭대기를 기준으로 s를 잘라놓고 생각하자. 왼쪽 산에 다음과 같은 그리디 알고리즘을 적용한다.

 

1. s에서 i개의 괄호를 가져와 올바른 괄호문자열을 유지하면서 열린 괄호의 개수를 늘릴 수 있는 i가 존재한다면, 최소 i만큼 괄호를 가져온다.

2. 그렇지 않다면, t에서 괄호를 1개 가져오고 다시 1을 진행한다.

 

예를 들어, s = "())(((", t = "(()"라고 하자.

그리디 알고리즘을 적용하면 다음과 같다.

1. s에서 괄호 1개를 가져온다. ans = "("

2. s에서 괄호를 가져와 이득을 볼 수 없기 때문에 t에서 괄호를 가져온다. ans = "(("

3. s에서 괄호 5개를 가져온다. ans = "(())((("

 

오른쪽 산의 경우, 방향만 바꿔서 동일한 알고리즘을 적용할 수 있다. 왼쪽 산에 알고리즘을 적용해서 얻은 문자열을 A, 오른쪽 산에 알고리즘을 적용해서 얻은 문자열을 C, t에 남아있는 문자열을 B라고 할 때, A, B, C를 이어 붙인 문자열이 올바른 괄호문자열일 때만 해가 존재한다. (증명은 생략한다.)

 

t에서 괄호를 가져오는 상황을 생각해보면, 현재 열린 괄호가 x개인데 이득을 보기 위해서는 열린 괄호가 y개가 필요한 상황이다. (x < y) 또한, 이러한 (x, y) 순서쌍은 여러 개 있다. 따라서, 다음과 같은 dp를 생각할 수 있다.

dp[i][j][k]: 현재 t에 괄호 i개를 추가했고, j번째 순서쌍을 보고 있으며, 열린 괄호의 개수가 k개다.

놀랍게도, state의 개수가 O(NM)이다. (증명은 생략한다.) 따라서, A에 쓰인 t의 문자가 i개인 경우의 수 $a_i$를 제곱에 구할 수 있고, C도 마찬가지다. (이를 $c_i$라고 하자.)

 

B의 경우, 간단한 dp를 통해 문자 i개를 썼을 때 경우의 수 $b_i$를 얻을 수 있다.

 

|A|+|B|+|C|가 m+n인 경우의 수를 구해야 하므로 $f = \sum a_ix^i$, $g = \sum b_ix^i$, $h = \sum c_ix^i$에 대해 $f*g*h$의 m차항을 구하면 된다.

 

BOJ 28085 (배 옮기기 (Hard))

모델링은 https://anz1217.tistory.com/161에 자세히 설명되어있다.

결국 간선 n-1개를 쓰는 최소 edge cover를 구해야 한다. 매칭에 있는 간선 개수를 1씩 늘리면서 그에 대응되는 edge cover에 대한 답을 전부 계산해 주면 O(N^3)에 풀 수 있다. 가중치 일반매칭에 대한 지식이 없어서 그냥 대충 코드보고 while문에 끼워 넣었더니 맞았다.

 

BOJ 30318 (제우스)

https://koosaga.com/295를 읽으면 좋다.

결국 각 센트에 대해 \sum min(a[i][0]+a[j][0], a[i][1]+a[j][1], a[i][2]+a[j][2])를 계산해야한다. a[i][0] + a[j][0] < a[i][1] + a[j][1]일 조건은 a[i][0] - a[i][1] < a[j][1] - a[j][0]이고, 2에 대해서도 마찬가지이므로 0이 최소인 경우의 수를 세는 것은 2D 쿼리임을 알 수 있다. 따라서 펜윅 들고 스위핑 해주면 로그제곱에 풀린다. 상수커팅하는 게 좀 힘들었다.

 

BOJ 15266 (Intrinsic Interval)

https://codeforces.com/blog/entry/78898를 읽으면 좋다.

위 글에서 "good range"를 "프레임 구간"이라고 부르겠다. 문제에서 묻는 것은 구간 [l0, r0]이 주어졌을 때 그 구간을 포함하는 최소 프레임 구간이다. 프레임 구간의 교집합은 프레임 구간이라는 좋은 성질을 이용하면, 다음 알고리즘을 생각할 수 있다.

 

1. r = r0로 설정한다.

2. [t, r]이 프레임 구간인 t <= l0가 존재하는지 체크한다. 존재한다면 최대 t일 때가 답이다.

3. 존재하지 않는다면, r을 1 늘려서 2번 과정으로 돌아간다.

 

2번 과정을 빠르게 하기 위해서는 적절한 자료구조가 필요한데, 내가 아는 대부분의 프레임 구간 문제는 seg[l] = max(P[l..r]) - min(P[l..r]) - (r-l+1)로 둔 min lazy seg로 풀린다. seg[l] >= 0이고, seg[l] = 0이라면 [l, r]이 프레임 구간이 된다. 세그를 갱신하는 방법은 min과 max를 담아둔 스택을 사용해서 구간 덧셈 업뎃을 해주면 된다. 자세한 설명은 코포 블로그 글에서 "Checking if there exists a good range" 파트 참고.

 

쿼리를 적절한 자료구조(나는 pq를 썼다)에 저장해 두고 하나씩 꺼내면서 세그 이분탐색을 통해 모든 쿼리에 대한 답을 계산할 수 있다. 전체 시간복잡도는 대충 O((N+Q)log(N+Q))다.