USACO 2023 January Contest

문제풀면서 생각나는걸 그대로 적다보니까 좀 길다.

즉, AC를 받기 전의 상태에서 계속 주저리주저리 한 것이다.

숫자들은 백준 기준. 티어는 굳이 언급하지 않겠다.

 

Silver.

 

#27558. Find and Replace

 

A를 첫 번째 문자열, B를 두 번째 문자열이라고 하자.

우선 당연하지만, A에서는 문자가 같은데, B에서는 문자가 다른 position이 존재한다면 불가능하다.

그렇다면 이제 각 52개 문자마다 바뀌고 싶은 문자 want[i]가 존재한다.

단, A에서 등장하지 않는 문자의 경우 want[i] = -1이다.

want[i] = x를 만족하는 i의 개수가 y개라고 하자.

제일 기본적으로 생각할 수 있는 변환 방식이 그냥 i -> x를 y번 진행해주는 것이다.

다만, 이것이 잘 안되는 경우가 존재하는데, want[x] != x인 경우이다.

단순하게 i -> x를 해버리면, 미래에 x를 다른 문자로 바꾸는데 어려움이 생긴다.

조금 더 생각을 해보면 a -> b -> c -> d -> -1이라면, 앞에서부터 순서대로 (c -> d), (b -> c), (a -> b)를 하면 된다.

 

하지만 문제가 생기는 상황은 cycle이 생기는 상황이다.

a -> b -> c -> d -> b인 상황이 존재한다고 가정하자.

이 경우에는 c -> a로 바꾸어버리면 되기에 아주 간단하게 cycle이 깨져버린다.

따라서 우리가 고려해야하는 cycle은 a -> b -> c -> d -> a로, 모든 점의 indegree가 1인 상황이다.

이 cycle을 깨기 위해선 이들과 무관한 e가 존재하여 (d -> e)로 cycle을 깨버리고 마지막에 (d -> a)를 해야 한다.

따라서 이 경우에 필요한 작업의 횟수는 1 더 증가하게 된다.

만일 이런 e가 존재하지 않는다면 이 작업은 불가능하다.

이런 e가 존재하지 않으려면 B에 52 종류의 문자가 모두 존재하면 된다.

 

#27559 Following Directions

 

N = 1500이라서 그냥 하면 될 것 같다는 생각이 든다.

 

우선 각 점 (i, j)마다 방향이 주어지므로, 그 방향으로의 간선을 만들어서 cow feed들이 root가 되는 그래프를 형성하자.

이제 child[i][j] = ((i, j)의 subtree에 존재하는 점들의 수)라고 정의하자.

그렇다면 우리는 (i, j)의 방향이 바뀐다면, 먹이값이 바뀌는 정도에 child[i][j]를 곱해주면 총 cost의 변화량을 알 수 있다.

(i, j)의 방향이 바뀌면 (i, j)의 parent도 바뀌기에, (i, j)의 모든 ancestor들의 child[i][j]도 변화한다.

이때 모든 점의 ancestor는 오직 O(N)개만 존재하므로 먹이값 변화, 모든 child[x][y] 갱신에 필요한 복잡도는 O(N)

따라서 총 복잡도는 O(NQ)이다.

 

#27560 Moo Route

 

대충 당연하지만, LLLLL을 최대한 지속하고 RRRR을 최대한 지속하는 것이 항상 이득이다.

우선 RRR...이 계속 가능한 만큼 계속 R을 출력하자.

그 다음에 LLL...을 출력하자.

이때 a[i] = 1인데 i < j인 j에 대해서 a[j] != 0이라면, L을 했을 때 j에 영원히 도달 못하므로 L을 그만 출력하여야 한다.

따라서 i > x인 모든 i에 대해 a[i] = 0을 만족하는 x의 최솟값을 관리해주면서 계속 RRR...., LLL...을 출력해주면 된다.

 

Gold.

 

#27558. Find and Replace

 

맨 마지막에 결과적으로 [L, R]이 될 부분을 잘 관리하면서 들고다니면 될 것 같다.

이걸 단순하게 [L, R]에 해당될 부분을 들고 다니면 복잡도가 1e8 내에 드는가?

단순하게 "aaaa...aaaa"가 있고 a -> b, b -> a를 계속 반복하기만 해도 문제가 생긴다.

그러면 과연 단순하게 '생성'되는 문자들의 수는 1e8 내에 들까?

결국에는 [L, R] 범위 내의 문자들만 들고 다니고, 해봐야 쿼리마다 양 끝에 하나씩 더 들고다니니, 무조건 가능하다.

 

즉 [L, R]이 될 부분을 들고 다니는 것 자체는 문제가 되지 않는데, (a -> b), (b -> a)의 변환이 문제가 되는 것이다.

그렇다면 이제 pos[i] = (현재 i인 position들)이라고 한다면, pos[a]와 pos[b] 사이에 small to large trick을 하면 된다.

 

#27556. Lights Off

 

신기하게도 N이 T에 앞서서 주어지기에 어떤 precalculation이 의심되는 형태이다.

아무튼 문제에서는 toggle이라고 나와있긴 하지만 사실상 XOR이기에 굳이 Off라는 개념으로 생각할 필요는 없다.

그리고 답이 그다지 크지 않을 것 같다는 생각이 든다.

-> 답은 대충 2N 이하이다.

-> 특정 위치 i의 불을 키고 싶다면 i번 스위치를 toggle하고 다음 번에 i + 1번 스위치를 toggle하면 된다.

-> 그러면 모든 (1 << n)개의 상태 i에 대해서 j번으로 만드는게 가능한지 나타내는 able[j][i]를 precalc하면 될 것 같다.

문제에서 주어지는 pair of string을 S, T라고 하자.

그렇다면 답이 1, 2, ... 이라고 가정해가면서 S ^ (T가 i번째에 미치는 영향) = U라 하면, able[i][U] = 1인지 확인하면 된다.

 

Precalculation을 어떻게 해야하는지 생각해보자.

단순하게 생각하면 able[j][i - 1] = 1인 모든 j들을 우선 가져온다.

그 다음에 i개의 연속된 비트로 이루어진 숫자 k들을 모두 가져온다 (ex) n = 3, i = 2면 011, 101, 110)

-> j들은 최대 2^N개 이고, k도 최대 N개. -> able[j ^ k][i] = 1이라고 설정하면 된다.

 

이렇게 O(N^2 * 2^N) precalculation해도 통과를 하는데, N = 20인 이상 아마도 정해는 N * 2^N일 것 같다.

N을 제거하는 방법은 다음과 같다.

만일 두 bitmask a, b가 서로 cyclic shift로 생성가능하다면, 반드시 able[a][i] == able[b][i]가 성립한다.

따라서 a에 대해서만 dp를 진행해주고, 나중에 나머지 shift N 종류들을 복구해주면 된다.

 

#27557. Moo Route

 

이번에는 가능한 Moo Route의 개수를 모두 세주어야 한다.

우선은 방향전환이 최소화 된다는 가정을 없애고 생각해보자.

그러면 모든 점에 대해서 (L, R)을 미리 배정해준다면 Bessie의 경로가 자동결정된다.

예를 들어, x = 0에 (R, R), x = 1에 (L, R, L), x = 2에 (L)이 배정되어 있다면, 경로가 저절로 RLRRLL로 정해진다.

cnt[i][L] = (i번 점의 L의 개수), cnt[i][R] = (i번 점의 R의 개수)라고 한다면

cnt[i][R] = cnt[i + 1][L], cnt[i][R] + cnt[i + 1][L] = a[i] 라는 두 식에 의해서 모든 점의 cnt[x][y]가 정해진다.

이때 무조건 x = 0을 제외한 점들의 마지막에는 L이 들어간다는 규칙만 지켜준다면, valid한 경로가 생겨난다.

따라서 모든 점 i에 대해서 C(L + R - 1,  R - 1)을 곱해주면 경로의 개수를 구할 수 있다.

 

위에서는 모든 점에 대해 (L, R)을 배정해주었는데, 이러면 방향전환을 고려할 수 없다.

따라서 이번에는 들어오는 방향까지 고려하자.

PQ라는 표현은 P 방향에서 들어와서 Q 방향으로 나가는 것을 의미한다고 하자.

그렇다면 모든 점에 대해 LL + RR의 합을 구하면 모든 방향전환의 횟수를 알 수 있다.

다시 식을 세워보면 (이번에는 들어오는 방향이 고려되기에, i번과 i + 1번의 cnt가 서로 관련이 없다)

1) cnt[i][LL] * 2 + cnt[i][LR] + cnt[i][RL] = a[i - 1]

2) cnt[i][RR] * 2 + cnt[i][LR] + cnt[i][RL] = a[i]

-> cnt[i][LL] + cnt[i][RR]을 최소화하려면 cnt[i][LR] + cnt[i][RL]을 최대화 해야하므로 min(a[i], a[i - 1])로 잡을 수 있다.

3) cnt[i][LR] = cnt[i][RL]  (이건 그냥 들어온 만큼 나가야 한다는 의미이다)

4) RL, RR에 대해서 RL이 반드시 맨 마지막에 배정되어야 한다.

그러면 이번에는 모든 점에 대해 C(LL + LR, LL) * C(RL + RR - 1, RL - 1)을 곱해주면 답을 구할 수 있다.

 

Platinum.

 

#27552. Tractor Paths

 

우선 a < c < b에 대해서 a와 b가 서로 adjacent하다면, a - c, c - b가 모두 adjacent하다.

X, Y 사이의 shortest path는 X에서 최소한으로 Y를 넘어가는 것과 같기에 a - b 대신 a - c를 선택할 이유가 없다.

따라서 shortest path length는 a - MAX(b)를 이어두고 sparse table 등으로 관리하면 쉽게 구할 수 있다.

문제는 special tractor의 개수이다.

어떤 Z가 special tractor이기 위해서는 X - Z + Z - Y = X - Y를 만족하면 된다.

따라서 O(N^2 + NQ)는 꽤 간단하게 풀 수 있다.

미리 N^2개의 쌍에 대해 최단거리를 Precalculation 해두고 나중에 쿼리당 O(N)으로 special을 찾으면 된다.

 

X -> Y로 가는 제일 오른쪽의 경로를 (X -> A -> B -> C -> Y)라고 하자.

Y -> X로 가는 제일 왼쪽의 경로를 (Y -> c -> b -> a -> X)라고 하자.

그렇다면 답이 되는 것은 [a, A] + [b, B] + [c, C]가 된다.

만일 모든 점이 special 하다면 (X + A + B + C + Y) - (X + a + b + c + Y) + (off by 1s)로 구할 수 있다.

psum[i]를 i번까지 있는 special 점의 개수라 하면 psum[A] + psum[B] + psum[C]를 구할 수 있으면 된다.

이것은 sparse table에 {도달 가능한 점, 도달하는 경로의 psum 값의 합}을 저장해서 관리해주면 된다.

 

#27553. Mana Collection

 

N = 18이면 bitmasking이 생각날 수 밖에 없다.

아무튼 굳이 아무 점에서 출발하여 s초에 e에 도달하는 것이 아니라, 0초에 e에서 시작하고 s초 동안 이동해도 된다.

그러면 적당한 경로를 돌면서 (e - t) * m[i]의 총합을 최대로 만들어야 한다. (단, t는 점 i에 최초로 도달하는 시점)

그러면 Naive하게 생각하자면 18! 종류의 경로들을 모두 해보면 된다.

이제 DP를 고려하기 시작한다면 겹치는 상황은 아마도 방문한 점의 set이 같고, 현재 있는 점이 같은 경우일 것이다.

즉, 어떤 점에 있는 상태를 (S, x, t)로 나타낼 수 있다. (S는 방문한 점들, x는 현재점, t는 도달하는데 걸리는 시간)

(S, x, t1) = a1과 (S, x, t2) = a2를 비교해보자.

이후로는 동일한 최적 경로로 갈 것이므로, 앞으로 방문할 점들의 m의 합이 M이라면, a - t * M으로 작용한다.

즉, 두 상태의 우위는 앞으로 방문할 점들의 집합에 따라서 결정된다.

따라서 만일 미래 방문할 점들의 집합이 left라면 상태를 (S, x, left)로 나타낼 수 있다.

이러면 상태 개수만 N * 3^N이고, dp의 상태전이를 고려하면 O(N^2 * 3^N)이 나올 것이다.

 

생각해보니 S를 굳이 고려할 필요가 없다. 즉, left가 같은 애들끼리만 비교해주면 된다.

따라서 상태의 개수는 N * 2^N이고, 상태전이를 고려하면 O(N^2 * 3^N)이다. 

그러면 쿼리 (s, e)에 대해서 MAX(dp[e][left] + s * (sum of mana of left))가 답이 된다.

-> 이건 MAX(a*s + b) 형태이기 때문에 CHT로 빠르게 처리할 수 있다.

 

근데 여기서 의문이 생길 수 있다. 경로에 걸리는 시간이 e 이하여만 하는것 아닌가?

경로에 걸리는 시간이 e를 넘어서면, 마지막으로 방문하는 pool은 음수로 작용하기에 그냥 방문 안하는게 더 이득이다.

따라서 굳이 이들을 제거해주지 않아도 이미 최선이 될 수 없기 때문에 상관 없다.

 

#27554. Subtree Activation

 

subtree들이 a[1], a[2], ... a[n] 순서대로 있다고 하자. (단, i번 subtree란 i번 노드 밑으로 있는 subtree)

그렇다면 우리의 목표는 sum(xor(a[i], a[i + 1])을 최소화하는 것이다. (단, a[0], a[n + 1]은 모두 꺼진 상태의 tree)

위의 값은 sum(a[i] + a[i + 1] - (a[i] & a[i + 1]))이므로, sum(a[i] & a[i + 1])을 최대화하는 것과도 동일하다.

만일 a[i]와 a[i + 1]이 어떤 관계도 없다면 0이 될 것이고, descendant라면 min(a[i], a[i + 1])이 될 것이다.

 

만일 a[i]가 x의 descendant이고 x가 a[i + 1]의 descendant라면, 이 사이에 굳이 x가 껴있지 않을 이유가 없다.

어차피 a[i]와 a[i + 1]의 중간에는 정확히 x인 상태가 존재하기 때문이다.

그렇다면 어떤 i가 존재하여 무조건 a[i] = 0일텐데, 이것의 양 옆에는 0의 child가 있다고 가정해도 문제가 없다.

-> 만일 아니라면, 그냥 0의 child를 억지로 0의 양 옆으로 옮겨도 필요한 toggle의 수가 증가하지 않기 때문이다.

동일한 이유로 1, 2가 0의 양 옆에 놓였다면, 1, 2의 옆에도 각각 1, 2의 child가 놓인다고 가정해도 상관 없다.

이것을 반복하면 (적당한 leaf) -> ... -> 1 -> 0 -> 2 -> ... (또다른 leaf)의 형태가 될 것이다.

이것을 위해 필요한 총 toggle의 횟수는 2 * (subtree[0]의 size)이다.

이후 아직 subtree[i] 였던 상태가 없는 i 중에 최댓값을 x라고 하자.

그러면 x에 대해서 정확히 똑같은 작업을 할 수 있다.

x였던 적이 없다면 당연하게도 x의 descendant였던 상태도 없기 때문에 완전히 똑같은 작업을 진행할 수 있다.

따라서 반복적으로 subtree[x] * 2를 더한 이 값을 최소화시켜주면 된다.

 

유의할 점이 있는데, 어떤 점 i에 대해서 양 옆에 놓이는 child가 동일한게 최선일 수 있다는 점이다.

즉 예를들어 그래프가 (1, 2), (2, 3), (2, 4)...의 형태일 때, 1의 양옆에 2를 2개 놓는 것이 최선의 상황일 수 있다.

이 경우에도 물론 subtree[x] * 2가 필요한 toggle의 횟수이다.

 

그러면 다음과 같은 tree dp를 떠올릴 수 있다.

dp[i][0] : i 밑의 어떤 leaf x에 대해 x의 모든 ancestor을 제외하고 각각의 상태가 한 번씩 있도록 하기 위한 최소 toggle 횟수

dp[i][1] : i 밑의 모든 subtree에 대해서, 각각의 상태였던 적이 한 번씩 있도록 하기 위한 최소 toggle 횟수

-> dp[i][0]는 dp[child][0]를 1개 선택한 형태이다. 나머지는 모두 dp[child][1]을 선택한다.

-> dp[i][1]은 dp[child][0]를 2개 선택하고 subtree[i] * 2를 더하여 아직 방문 안한 상태를 모두 방문한 형태이다.

-> dp[i][1]은 이것 외에도 모두 dp[child][1]을 선택하고, (subtree[i] - subtree[child]) * 2가 더해진 특수 케이스가 존재한다.