NYPC 2019 예선 풀이 3~5일차

3-1 가위바위보

문제 설명 생략.

 

가위바위보 결과로 $(a,b)$가 들어오면 다음 3개의 작업을 해준다.

1. a와 b가 속한 집합을 합쳐준다.

2. win[a]값을 1 증가시킨다.

3. lose[b]값을 1 증가시킨다.

1번 작업은 Union-find를 이용하여 할 수 있다.

 

이제 모든 집합들 중 사이즈가 가장 큰 것들 중에서 승자를 고르고, 이들 중에서 가장 index가 작은 애가 우승자다.

 

3-2 넥슨 사진관

크기가 $N$인 자연수 배열 $A$가 주어진다. 쿼리도 $Q$개 주어진다. 쿼리는 다음과 같은 작업을 한다.

$1$ $a$ $b$ : $A[a]=b$로 바꾼다.

$2$ $a$ $b$ : 구간 $[a,b]$를 이용하여 팰린드롬을 만들 때 가운데 오는 수를 출력한다.(답이 존재함이 보장된다.)

 

팰린드롬을 만들기 위해서는 홀수개 존재하는 수가 1개이거나 0개여야 한다. 문제에서 $b-a+1$이 홀수이고, 항상 답이 있다는 사실은 보장됨이 주어졌기 때문에 무조건 1개만 나온다는 게 보장된다.

 

그럼 어떤 수가 짝수개 있을 땐 무시되고, 홀수개 있을 땐 그 값이 무엇인지 알 수 있으면 된다.

이는 xor연산을 통해 알 수 있다. 그리고 구간 xor연산 및 업데이트를 Fenwick tree 또는 Segment tree를 이용하여 구현하면 된다.

 

3-3 회 문화의 회문화

어떤 문자열 $S$가 있다. 앞의 몇 글자를 떼서 뒤에 붙이는데, 이때 팰린드롬이 되는 경우가 몇 가지인지 구하는 문제다.

 

문자열의 길이를 $N$이라고 하자. 그리고 $S$를 복제하여 그 뒤에 붙여 넣자. ( ex : abca → abcaabca ) 이걸 $N$글자씩 끊어서 팰린드롬인지 아닌지 확인하면 된다. 어떤 문자열에서의 구간 $[l,r]$이 팰린드롬인지 아닌지 $O(1)$에 확인하는 방법은 크게 2가지(manacher algorithm, 해시)가 있는데, 나는 해시충이기 때문에 해시로 풀었다. (라빈-카프 알고리즘을 이용해서 풀었다. 라빈-카프 알고리즘에 대해 자세한 내용은 위 링크에서 공부하도록 하자.)

 

해시테이블을 양방향으로 저장해주고, 두 테이블에서의 $hash(l,r)$값이 일치하면 구간 $(l,r)$은 팰린드롬이다. 따라서

$k$를 0부터 $N-1$까지 순회하면서 $hash(k,k+N-1)$이 일치하는 개수를 구해주면 된다.

 

4-1 VIP 쿠폰

쿠폰이 $N$개 있다. 각 쿠폰은 $E_i$와 $D_i$값이 존재하는데, 각각 쿠폰의 유효기간과 적용기간을 의미한다. 이때 최대 며칠간 VIP생활을 누릴 수 있는지 묻는 문제다.

 

Subtask 1,2번과 3번은 풀이가 전혀 다르다. 그래서 어쩔 수 없이 둘 다 써야 한다.

 

Subtask 1,2 ($N \leq 20$, $E_i$, $D_i \leq 10^8$)

$N$제한만 봐도 bitmask dp로 풀어야 될 거 같이 생겼다. 현재 상태 값을 $K$($i$번 째 비트가 켜져있으면 $i$번 째 쿠폰은 사용한 것이고, 꺼져있으면 아직 사용을 하지 않은 것)라 하고 풀어보자. $K$ 상태에서 쿠폰의 지속시간은 켜져있는 비트들의 $D_i$값의 합으로 계산할 수 있다. 다음에 이용할 수 있는 쿠폰은 $E_i$값이 저 값보다 높은 쿠폰이고, 그러한 쿠폰이 있으면 상태값을 옮겨가며 dp테이블을 채워주면 답을 얻을 수 있다.

 

Subtask 3($N \leq 10^3$, $E_i$, $D_i \leq 10^5$)

결론부터 말하자면 냅색 문제다. 그냥 냅색을 하면 안 되고 쿠폰들을 적당하게 정렬해서 냅색 해야 한다.

그리고 솔직히 말하면 적당한 정렬의 엄밀한 증명을 못하겠다. 직감과 경험에 의해서 $E + D$가 작은 순으로 정렬해서 냅색 했다. ("E+D가 같을 때 서로에게 영향을 못주는 건 자명하고, E + D가 커야 더 뒤에 있는 비트를 더 멀리 보낼 수 있는 거 아니야??")

저도 양심이란 게 있기 때문에 자세히 쓰진 않겠습니다. 그냥 저렇게 정렬하고 순서대로 냅색 하면 $O(NE)$에 풀 수 있습니다.

 

4-2 빨간점 파란점

빨간 점 $R$개와 파란 점 $B$개가 있다. 점들의 모양을 볼록 껍질 형태임이 보장된다. 주어진 점들로 스패닝 트리를 만드는데, 간선의 양끝 점은 서로 다른 색이어야 하고 간선끼리 교차하면 안 된다. 두 점 $i$와 $j$을 연결하는 비용을 $abs(x_i - x_j) + abs(y_i - y_j)$로 정의한다. 이때 트리를 만드는 최소비용을 구하는 문제다.

 

문제에서 볼록 껍질 형태로 주어진다고 했으므로 마음 놓고 점을 각도 순으로 정렬해보자.

 

그다음 작은 관찰을 해보자.

위와 같이 점들이 있다고 하자. 여기서 색이 서로 다른 두 점을 이어 보면 어떤 결과가 생기는지 확인해보자.

 

이렇게 두 점을 이은 다음에는 어떤 식으로 연결을 해야 할지 감이 잡힐 것이다. 

빨간 박스 안에 있는 점들은 그 안에서만 연결이 돼야 하고, 파란 박스 안에 있는 점들도 마찬가지다. 그리고 각 박스 안에 있는 점들도 항상 볼록 껍질을 유지한다. 즉, 전체 문제의 부분 문제를 푸는 모습으로 바꿀 수 있다. 우리는 이걸 DP를 이용해서 풀 것이다.

여기서 또 하나의 관찰. 어떤 간선을 기준으로 부분 문제를 만들었을 때, 다음에 잇는 간선은 반드시 그 간선의 양 끝점 중 하나는 반드시 연결을 해야 한다. 그래서 다음과 같은 dp식을 세울 수 있다.

 

• $dp[i][j]$ = $i$번 점과 $j$번 점이 연결돼있을 때, $i$번 점부터 $j$번 점까지 이용하여 트리를 만드는 최소비용

$k$를 $i+1$부터 $j-1$까지 돌다가 $k$점과 $i$점의 색깔이 다르다면 $dp[i][j]=dist(i,k)+dp[i][k]+dp[k][j]$ 처럼 업데이트 해주면 된다.($j$점과의 비교도 마찬가지)

 

점이 요따구로 연결돼있을 때 파란 박스 안에는 어떻게 처리해요??

똑같이 처리하면 된다. 서순의 차이일 뿐, 결과는 같게 나온다.

 

참고로 저는 $R+B \leq i < 2*(R+B)$에 대해 $p[i]=p[i-R-B]$를 해서 뒤에 복사했고, $dp[i][j]$에서 $i \geq j$인 경우는 $j=j+R+B$로 계산해서 항상 부분 문제 푸는 방향이 동일하도록 했습니다.

 

4-3 메이플스토리 연주회

몬스터가 $N$마리는 각각 부르는 문자열 노래 $S_i$가 있다. 어떤 스토리였는지 기억이 안 나는데 아무튼 문자열 $P$가 주어진다. 몬스터들이 노래를 적당히 순서 바꿔가며 부를 때, 그 노래들을 이어 붙인 문자열이 $P$가 되는 경우의 수를 구하는 문제다.

 

이 문제는 트라이를 이용해서 dp로 풀 수 있다. 다음과 같은 식을 세워보자.

$dp[i]$ = 문자열$P$의 $i$번 째부터 시작해서 끝을 볼 수 있는 경우의 수

그리고 몬스터들의 모든 노래를 트라이에 저장하자. 그러면 다음과 같은 과정을 통해 답을 구할 수 있다.

1. 현재 노드의 자식 노드로 $P[i]$가 존재한다면 그 노드로 내려가고 (노드의 valid값 $\times$ $dp[i+1]$)을 결과에 더해준다.(valid값은 추후 설명)
2. 없다면 바로 현재까지의 결과를 리턴

이렇게 두고 트라이를 계속해서 순회하며 답을 갱신해주면 답을 구할 수 없다

 

몬스터의 노래가 AAAAAAAAAAAA..... 이고 $P$도 AAAAAAAAAAAA..... 이면 정말 엄청난 시간이 걸리게 된다. 이를 최대한 최적화해야 한다.

 

문제의 예제를 트라이로 표현하면 다음과 같다.(AB, ABCA, CA)

여기서 노란색 노드는 valid한 노드로, "여기까지 노래를 부른 몬스터가 있어요!!!"를 표시해준다. 같은 노래를 부른 몬스터가 있을 수 있기 때문에 int형으로 몇 마리의 몬스터가 거기까지 노래를 불렀는지 저장해준다. 여기서 하나 의구심을 가져보자. 저 검은색 노드 3개는 과연 크게 의미가 있는 노드일까? 답은 "아니오"다. 저렇게 valid하지도 않고 자식 노드의 개수가 1개뿐인 노드는 dp 계산하는데 의미도 없고, 다음 노드도 정해져 있기 때문에 굳이 탐색을 안 하고 다음으로 건너뛰어도 아무 문제가 없다. 이걸 압축해서 아래처럼 만들면 탐색 속도가 훨씬 빨라지지 않을까?

트라이의 깊이가 4에서 2로 줄었음을 알 수 있다. 즉, $dp[i]$를 계산하는데 확인해야 하는 노드의 개수가 4개에서 2개로 줄었다.

 

깊이는 확실히 줄긴 줄었는데 상한 값을 모르면 아무 의미가 없다. 깊이가 가장 깊은 경우는 몬스터들의 노래가 (A, AA, AAA, AAAA, ....)꼴인 경우이고 이때 깊이는 $\sqrt{|S|}$이므로 시간복잡도 $O(|P|\sqrt{|S|})$로 풀 수 있다.

 

압축은 모든 노드에 대해서 dfs를 해서 다음 노드, 압축된 길이, 압축한 문자열을 저장해주면 된다. 나는 해시충이기 때문에 압축한 문자열 역시 해시값으로 저장했다.

 

p.s. 아호코라식으로 풀 수 있다고 합니다.

 

5-1 메이플스토리 파티 구성

길드원 $N$명이 있다. 길드원끼리 파티를 구성하는데, 직업의 수는 상관없이 직업의 종류가 같으면 같은 파티 구성을 이룬다고 한다. 쿼리 $Q$개 가 $a$ $b$ $c$ $d$ 꼴로 주어지는데, $a$번 길드원부터 $b$번 길드원까지 파티를 맺고, $c$번 길드원부터 $d$번 길드원까지 파티를 맺었을 때 두 파티가 같은 파티 구성을 이루는지 묻는 문제다.

 

$Q$개의 쿼리를 나눠서 각각 $2\times Q$, $2\times Q+1$번 쿼리로 바꾸자.

그다음은 웰노운 오브 웰노운 Mo's algorithm으로 처리하자.

 

파티 구성 상태를 $O(1)$에 업데이트하고 비교할 방법을 구해야 되는데 또 해시를 이용해서 구해주면 된다. 나는 파티에 구성된 직업 구성을 $S$라 했을 때 $x\in S$에 대해 $(\sum x!)\%MOD$값을 해시값으로 사용했다. (이것 외에도 각 직업에 적절한 소수들을 매칭 시켜 곱하고 나누거나 등등.. 편한 대로 하면 된다.)

 

Mo's algorithm을 돌렸으면 이제 아까 나눴던 쿼리들을 다시 보자. $0\leq i<Q$를 만족하는 $i$에 대해 $ans[i*2]$와 $ans[i*2+1]$의 값이 같으면 YES 아니면 NO를 출력해주면 된다.

5-2 카트 발사

직교 다각형이 주어지고 처음 킹오의 위치, 초기 이동방향이 주어진다. 킹오는 직교 다각형의 각 변과 만나면 입사각과 반사각이 같은 상태로 방향을 전환한다. 이 때, 처음으로 세로선과 만나는 $x$좌표가 어디인지 구하고 거기서 처음 킹오 위치의 $x$좌표를 빼주면 되는 문제다.

 

참고로 풀려고 할 때 사지방이 터져서 아쉽게도 코딩을 못한 불운의 문제다. 그래서 확실히 푼 문제가 아니기 때문에 대략적인 풀이 개요 설명만 할 것이다.

 

이 문제에서 정말정말정말 중요한 점이 있다. 직교 다각형의 각 점과 처음 킹오 위치의 모든 $y$좌표의 스케일을 $dx$배를 해주자. 그럼 놀랍게도 $dx$의 값은 1로 고정되고 그 이후는 단순 수학 및 구현 문제로 치환된다.

 

갑자기 뜬금없지만 다음 문제를 풀어보자.

직사각형 안에 있는 검은색 점이 화살표 방향으로 이동할 때, 처음 오른쪽 변에 닿는 $y$좌표는 과연 어디일까? (단, 점이 변에 닿으면 입사각과 반사각이 같도록 방향을 바꾸어 계속 진행한다.)

각 점과 변의 좌표를 알고 있다면 위의 그림처럼 가상의 공간을 만든 뒤에 반사시키면 적당한 수식으로 구할 수 있다.

 

이걸 왜 설명하냐면 문제에 주어진 모든 공간을 세로선을 기준으로 직사각형으로 잘게잘게 잘라낼 것이다. 이게 무슨 소린가 싶겠지만 사실 세로선만 이용하면 이 작업을 그리 어렵지 않게(?) 할 수 있다. 모든 세로선의 $x$ 좌표와 양 끝점만 map 같은 곳에 저장하고 스위핑 해주며 끝점을 업데이트하면 비교적 편하게 구현할 수 있다. 그 작업을 완료하면 위에서 설명한 문제를 세로선에 닿을 때까지 반복해주면 된다.

 

예시를 들어보자.

위의 그림 같은 문제가 있다고 하자. 그럼 아래처럼 다각형을 직사각형들로 나눠준다.

그다음부터는 순서대로 그림으로 보여주겠다.

 

이런 과정들을 거치면 처음 세로 변에 닿는 $x$좌표의 위치를 구할 수 있을 것이다.