AtCoder Regular Contest 164
https://atcoder.jp/contests/arc164/tasks
B가 말린 관계로 점수가 떨어졌다.
C, D 그리고 확실하진 않지만 E까지 꽤 쉽게 나온 것 같다.
A. Ternary Decomposition
당연히 K의 최솟값은 N을 3진법으로 나타냈을 때 모든 자리수의 합이다.
이때 제일 큰 3^m을 잡고 이를 3^(m - 1) 3개로 바꾸어주면 사용하는 3^x의 개수를 2 늘릴 수 있다.
따라서 K가 N을 3진법으로 나타냈을 때의 자릿수의 합보다 크거나 같고 기우성만 같으면 표현이 가능하다.
B. Switching Travel
문제에서 원하는 어떤 cycle이 존재한다고 가정하자.
그렇다면 cycle 위의 아무 점을 잡고, 색깔이 다른 이웃한 간선으로 이동하는 DFS를 돌린다면,
cycle은 일직선으로 쭉 내려가다가, 위쪽으로 가는 간선을 타고 올라오는 형태일 것이다.
즉, 색깔이 다른 이웃한 간선으로만 가는 DFS를 굴렸을 때, 동일 색의 ancestor로 가는 간선이 있는지 확인하면 된다.
모든 점을 root로 할 필요는 없고 한 번씩 방문만 하면 되기에 O(max(N, M))
C. Reversible Card Game
이해의 편의를 위해서는 카드가 3장일 때의 상황을 여러 번 생각해보는 것이 좋다.
각 카드를 그냥 한쪽 면에는 A - B, 다른 쪽 면에는 0이 있다고 생각하자. (마지막에 답에 B를 모두 더해주자)
A - B의 값들 중 음수의 개수를 M이라고 하자.
1) N, M의 기우성이 같다면
-> Alice는 반드시 뒤집어야 하므로, Bob이 받는 시점에는 N, M의 기우성이 다르고, Bob은 항상 양수만 고르면 된다.
2) N, M의 기우성이 다르다면
-> Bob은 적어도 하나의 음수를 골라야 한다.
-> 당연히 Bob은 제일 큰 음수를 고르고 싶을 것이고 이 값을 X라고 하자.
-> X가 앞면이면 Bob은 그냥 X를 고르고, 앞으로는 항상 1)과 같이 양수가 존재하기에 양수만 고르면 된다.
-> X가 뒷면이면, 기우성에 의해 어떤 다른 음수가 함께 뒷면이기에, 그 음수의 뒷면(= 0)을 고르면 된다.
따라서 Bob은 max(A - B, 0)을 모두 고르거나, 손해를 봐도 딱 한 번만 손해를 본다.
D. 1D Coulomb
전하들을 관찰했을 때 괄호와 비슷하다는 느낌이 든다.
예를 들어 +를 '(', -를 ')'로 표현했다고 하자.
이때 T = ( ~ ) / ( ~~ ) 형태라고 가정했을 때, 만일 올바른 형태의 괄호라면, 충돌은 각각의 괄호 내에서만 이루어진다.
그러면 이제 정확히 어떤 T가 주어졌을 때의 결과값이 어떤지 보자. (일단은 '?'가 없는 경우)
우리는 괄호질을 할 때와 마찬가지로 '+' = 1, '-' = -1을 이용하여 T에서 Prefix sum들을 구할 수 있다.
prefix_sum[i] = x라고 하자.
그렇다면, prefix_sum[i] 직전의 prefix_sum[j] = x인 j가 존재한다면, (j - i) 만큼의 이동 끝에 이 둘은 서로 충돌한다.
따라서 prefix_sum[p] = q인 p가 등장할 때마다, q가 홀수 번째로 등장하면 -p, 짝수 번째로 등장하면 +p를 해주면 된다.
-> 즉 prefix_sum[i] = prefix_sum[j] = x에서 i가 답에 기여하는 값인 +i or -i는 j의 값과는 독립하다는 의미이다.
이제 '?'가 있는 상황을 위해서 dp를 설계하자.
dp[i][j].first = (i번 전하까지 고려하였을 때 prefix_sum[i] = j인 상황의 개수)
dp[i][j].second = (i번 전하까지 고려하였을 때, prefix_sum[i] = j인 상황들에서 전하 이동 거리의 합)
편의를 위해서 '+'가 오는 상황만 고려하자. ( '-'는 정반대로 해주고, '?'는 +, - 둘 다 해주면 된다.)
1) j < 0
dp[i + 1][j + 1].first += dp[i][j].first -> 이건 당연하다. (i, j)에서 '+'를 붙이면 (i + 1, j + 1)로 이동하기 때문.
dp[i + 1][j + 1].second += dp[i][j].second + i * dp[i][j].first -> (i, j)에서 j가 음수이기에 i은 짝수 번째로 prefix_sum = j + 1이다
2) j >= 0
dp[i + 1][j + 1].first += dp[i][j].first
dp[i + 1][j + 1].second += dp[i][j].second - i * dp[i][j].first -> 이번에는 i가 홀수 번째로 j + 1에 도달하였으므로 빼준다.
DP를 끝까지 계산해주면 dp[2n][0].second가 답이 된다.
E. Segment Tree Optimization
우선 만일 x와 x + 1을 분리시키는 쿼리가 없다면, 어차피 x가 leaf이거나 x + 1이 leaf인 노드로는 가지 않는다.
따라서 모든 쿼리에 대해서 분리되는 (L - 1, L), (R, R + 1)을 고려하여 숫자들을 구간별로 새롭게 나누어주자.
이때 diff1[X] = (X는 포함, X - 1은 비포함 쿼리의 횟수), diff2[X] = (X는 포함 X + 1은 비포함 쿼리의 횟수)라 하자.
우선은 d를 최소화시켜보자.
적당한 d값에 대해서 모든 구간들은 반드시 깊이 d 이하에 존재하여야 한다.
왜냐하면 X번째 구간은 X + 1번째 구간과 반드시 구분되기에 무조건 investigation이 모든 구간에 들어가기 때문이다.
이때 깊이 d에 존재할 수 있는 구간은 2^d이므로 (구간의 개수) <= 2^d가 되는 최소의 d를 잡아주면 된다.
이제 c를 최소화시키자.
다음과 같은 경우에는 d 깊이의 노드에 investigation이 들어오지 않는다.
1) X번 구간이 그냥 d - 1이하의 깊이에 존재한다.
-> 단순히 모든 X를 d - 1에 박을 수는 없고, 최대 2^d - (구간의 개수) 만큼 d - 1 깊이에 둘 수 있다.
2) X, X + 1 구간이 d 깊이에 존재하며 부모가 같을 때, (X, X + 1)을 구분하지 않는 쿼리라면 들어오지 않는다.
-> 즉 diff1[X + 1] + diff2[X]에 대해서만 X번 구간, X + 1번 구간으로 investigation이 들어온다.
따라서 다음과 같은 DP를 설계할 수 있다.
dp[i][j] : i번까지 고려했을 때 j개의 구간을 d - 1 깊이에 두었을 때 최소 investigation의 횟수
1) i번 구간을 d - 1 깊이에 놓는 경우
-> dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j])
2) i번 구간을 i + 1번 구간과 함께 d 깊이에 놓는 경우
-> dp[i + 2][j] = min(dp[i + 2][j], dp[i][j] + 2 * (diff2[i + 1] + diff1[i]))
d - 1 깊이에는 구간을 2^d - (구간의 개수) = left만큼 넣을 수 있으니 min(dp[(구간의 개수)][x <= left])의 값을 구하면 된다.
cf1) 위의 dp를 그대로 역추적해주면, 문제에서 원하는 binary tree를 construction하는 것이 가능하다
cf2) N = 2e5라면 어떻게 풀 수 있을까? (불확실함)
-> dp의 형태가 monge한 형태이기에 dnc optimization이 (아마도) 될 것이다.