ABC 397

 

https://atcoder.jp/contests/abc397

 

 

 

Performance Rating : 2335

 

A

기본적인 대소관계 비교 문제였다.

 

B

$i$번째와 $(i+1)$번째 사이에 문자를 삽입하면 $1$부터 $i$번째까지 문자의 위치에는 영향을 주지 않기 때문에 앞에서부터 채워 나가야겠다는 생각으로 풀었다.

 

C

가장 처음 생각난 풀이는 레이지 세그먼트 트리였으나 조금 더 생각을 해보니 각 숫자의 개수를 세어두면 $A_1$부터 차례로 보면서 왼쪽과 오른쪽에 있는 숫자 종류의 개수를 $O(1)$의 시간에 구할 수 있다.

 

D

처음에는 풀이가 떠오르지 않았다. 투 포인터로 $x$, $y$를 찾아나가는 풀이가 가능한지 생각하기 위해 가능한 $x$의 범위를 생각해 보기로 했다. $(x+1)^3-x^3=3x^2+3x+1$이므로 $x$가 최대 $10^9$스케일까지 가능하다는 것을 알게 되었고 투 포인터 풀이를 포기했다. 생각을 하던 중 $x^3-y^3=(x-y)(x^2+xy+y^2)$이라는 사실을 활용해 $x-y\leq 10^6$이라는 사실을 알 수 있었다. $x-y$의 값을 1부터 $10^6$까지 증가시키면서 $N=0(\mathrm{mod}\;i)$인 $i$에 대해 이분탐색으로 $(x^2+xy+y^2)=N/i$인 $y$의 값을 찾는 방식으로 문제를 해결했다.

 

E

tree dp아니면 방법이 없어 보였다. dp를 어떻게 짤지 고민하던 중 $dp[i]$에 $i$ subtree를 $K$개의 path로 분할하고 남은 route의 길이라고 정의했다. 자식 중 $dp[i]>0$인 자식의 개수가 3개 이상이라면 불가능하고, 2개라면 $1+dp[i]+dp[j]=K$를 만족해야 하며 1개이면 $dp[p]=(dp[i]+1)(\mathrm{mod}\;K)$, 0개이면 $dp[p]=1$이 된다.

 

F

C를 3개로 나누는 문제이다. 처음에는 레이지 세그 트리를 사용해서 개수가 3개 이상인 수의 최소, 최대 인덱스 사이에 2를 더하고, 2개인 수의 최소, 최대 인덱스 사이에 1을 더하는 말도 안되는 풀이를 작성했다가 지웠다. 고민을 해보다가 자르는 2개의 위치를 정했을 때 양끝에 있는 수열에서 서로 다른 숫자의 개수는 미리 계산해 둘 수 있다는 사실을 알게 되었고 $A_1$부터 $A_i$까지 서로 다른 수의 개수를 $pre[i]$, $A_i$부터 $A_N$까지 서로 다른 수의 개수를 $suf[i]$에 저장해 두었다. 이제 가운데 수열에서 서로 다른 수의 개수가 중요해졌는데 개수 자체는 레이지 세그먼트 트리를 사용하면 구할 수 있다는 것을 알게 되었다. $i$를 1부터 $N$까지 증가시키면서 $j<i$이면서 $A_i=A_j$인 $j$의 최댓값을 구해 $v_j$부터 $v_i$까지 1을 더해주면 $v_j$는 $A_{j+1}$부터 $A_i$까지 서로 다른 수의 개수를 의미한다. 근데 중요한 것은 3개의 합이므로 레이지 세그먼트 트리에 $pre[i]$를 미리 넣어두고 위의 과정을 수행하면 $A_1$부터 $A_i$까지의 수열을 2개로 나누었을 때 서로 다른 수의 개수 합을 $O(logN)$에 구할 수 있다는 것을 알게 되었고 이를 통해 해결했다.

 

G

max flow min cut을 사용하면 최소 경로의 길이를 1로 만드는 데 필요한 개수가 나온다. 이를 확장하여 풀이를 작성하려고 했는데 실패했다.