SWERC 2020

이 셋(백준, 코포)을 가지고 팀연습을 했다.

https://blog.naver.com/hibye1217/223120058054 (팀원 후기 참고)

놀랍게도 이번에는 5시간 동안 단 5문제 읽었고, 실질적으로 1문제 풀었다.

나 자신의 퍼포는 맘에 들지 않지만 팀원이 캐리해서 팀적으로는 퍼포가 나쁘지 않다.

 

K. Unique activities

 

문제를 읽자마자 일단 풀이는 떠올렸다.

Suffix array를 구현하던가, 아니면 해싱으로 이분탐색을 하거나.

전자는 너무 오래걸릴 것 같아서 준서한테 풀이를 알려주고 구현해달라고 했다.

 

 F. Mentors

 

이게 원래 백준에서 다5였고, 정해도 다5에 가까운 문제일 것이다.

다만 대시보드에서 생각보다 많이 풀림 + 난이도를 알 수 없음 에 의해서 이것이 쉬운 문제일 것이라 판단했었다.

그리고 쉬운 풀이가 나왔다.

 

dp[a][b] = (자식자리가 2자리 남은게 a개, 1자리 남은게 b개)

그러면 맨 처음에는 상상속의 n + 1번 노드를 만들어 dp[0][1] = 1이라고 생각할 수 있다.

이제 n번 노드부터 순서대로 노드들을 추가해 나가면 된다.

그러면 dp[a][b] = c라면

1) 자식이 2인 것에 추가 -> nxt_dp[a][b + 1] += c * a

2) 자식이 1인 것에 추가 -> nxt_dp[a + 1][b - 1] += c * b

와 같이 dp를 진행할 수 있다.

 

내가 이 문제가 절대 다이아가 아니라고 하면서 남들을 보여주니, 남들도 그에 상응하게 쉽게 풀고, 플레로 바뀌었다.

 

I. Emails

 

문제를 잘못 읽었다.

문제에서 구하는 것이 log(Max_length)인데, Max_length / 2라고 착각하여서 망했다.

참고로 아마도 Max_length를 구하는 것은 불가능할 것이다.

 

J. Daizy's Mazes

 

Deck을 들고 다니면서 DP를 하는 것은 너무 어렵다.

아무리 상수들이 작다하더라도 deck은 중복 가능 + permutation 이라는 문제가 있기 때문이다.

그리고 실제로 대회중에는 왜인지 답이 되는 경로가 그리 길 것 같지 않아서 무지성 시뮬레이션도 굴려봤다.

대충 test 8까지는 뚫어버리는데 그 이후는 뚫리지 않는다.

 

그래서 deck이 항상 비어있는 경우만 생각하자.

우선, 문제의 상황을 (빈덱) -> (빈덱)으로 바꾸어버리자.

이것은 가상의 정점들을 더 만듦으로써 가능하다.

문제에서 주어지는 정점이 0 ~ n - 1인데 일단 n ~ 2n - 1로 이름을 바꾸자.

1) 0 ~ n - 1까지 n개의 정점을 추가하여, i번에서 i + 1번으로는 모든 c색의 간선이 있다고 가정하자.

-> 그렇다면 i -> i + 1로 가는 것은 그냥 자신이 원하는 색의 카드를 추가하는 행위라고 생각할 수 있다.

-> 즉, 답이 되는 덱이 x장이라면 그냥 n - x번 정점부터 순서대로 x장을 추가해주면 된다.

-> 단 이 정점들에서는 덱의 맨 위에 있는 색과 대응되는 간선이 있더라도 그 간선을 탈 필요가 없다고 가정하자.

-> 답이 되는 값은 n보다 작기 때문에 n개의 정점만 추가하면 된다.

2) 2n ~ 3n - 1까지 n개의 정점을 추가하여 마찬가지로 i번에서 i + 1번으로는 모든 c색의 간선이 있다고 가정하자.

-> 그러면 i -> i + 1로 가는 것은 자신의 덱 맨 위에 있는 카드를 제거하는 행위라고 생각할 수 있다.

-> 즉 마지막 2n - 1번 노드에서 덱에 몇 장이 남았을 때, 그냥 더 진행함으로써 덱을 비울 수 있다는 뜻이다.

 

이제 다음과 같은 dp를 정의하자

dp[i][j][k] = (i번 정점에서 k가 맨위에 있는 덱을 들고 있다면, 그대로 j번 정점에서 이 덱을 그대로 유지할 수 있는가)

이때 k = c인 경우도 만들건데, c번 색은 존재하지 않으므로 그야말로 빈 덱을 의미한다.

따라서 dp[i <= n][j >= 2n - 1][c] = 1인 최대한 큰 i를 찾으면 된다.

dp는 다음과 같은 방식으로 전파된다.

1) dp[i][x][k] && dp[x][j][k] 라면 dp[i][j][k] = 1

2) dp[i][j][k] = 1일 때 {u, i, k}, {j, v, k}인 간선이 존재한다면 dp[u][v][k'] = 1

-> 단, 이때 u에서 k'을 가진채로 {u, i, k}를 탈 수 있어야 한다.

-> 즉 u < n이 성립하거나 u에서 나오는 간선 중에서 k'색을 가진 간선이 없어야 한다.

 

그러면 아까 말한대로 dp[i <= n][j >= 2n - 1][c] = 1인 최대한 큰 i가 x라면

답이 n - x가 된다.

x에서부터 차례대로 잘 덱을 쌓은 다음에 적당히 2n - 1을 지나 j로 가는 것이 최선이기 때문이다.