AtCoder Regular Contest 178

https://atcoder.jp/contests/arc178/tasks

조오금 말렸지만 D를 시간 내에 다행히 풀어냈다.

 

A. Good Permutation 2

 

우선 불가능한 경우는

1) A[i] = 1이 있는 경우

2) A[i] = N이 있는 경우

특정한 A[i] 길이의 permutation이 없다는 뜻은 이들 중 하나가 뒤쪽으로 밀려났다는 뜻이다.

혹은 A[i] + 1이 반드시 1 ~ A[i]에 존재한다고 볼 수 있다. (Lexicographically smallest라는 조건에 의해)

따라서 A를 모두 정렬한 뒤, 기본 I = {1, 2, ... N} 배열에 대해 swap(A[i], A[i] + 1)을 차례대로 진행하면 된다. 

 

B. 1 + 6 = 7

 

신나는 케이스 워크를 각각한다. WLOG A1 >= A2는 걸고 가자

1) A3 = A1, A2 = A1

2) A3 = A1, A2 < A1

3) A3 = A1 + 1, A2 = A1

4) A3 = A1 + 1, A2 < A1

케웤 실수를 너무 많이해서 시간을 오래 끌었다.

 

C. Sum of Abs 2

 

B가 정렬되어있다고 쳐도 상관 없다

-> 0, a1, a1 + a2, ..., a1 + a2 + a3 + .. + a[L - 1] 이라고 치자

-> 그러면 값은 A = SUM( i * (L - i) * a[i] )이고 a의 합을 최소화하면 된다

 

느린 풀이 : dp[x] = (x에 도달하는 최솟값), dp[x] = min(dp[x - i * (L - i)] + 1) O(MAX * L)로 냅색을 돌면 된다

빠른 풀이 : 냅색을 할 때 x - i * (L - i)가 양수인 점으로만 넘어갈 것이다.

-> 따라서 i는 어차피 sqrt(x) 정도 이하 이므로 그냥 냅색도 break를 쓰면 빨리 돈다. 

-> 즉, 그냥 나이브한 냅색에 break만 적당히 걸어도 O(sqrt(MAX) * L)로 돈다.

 

D. Delete Range Mex

 

결국 삭제된 값 i는 어떤 구간 [L, R]에 대해서 mex가 정확히 i인 순간이 있어야 한다.

제일 큰 것부터 지운다고 생각하면 맨 처음 순열에 그런 구간이 존재하면 됨을 확인할 수 있다.

 

우선 (A1, A2, .. AM)이 그대로 남는 것이 아니라 아무 순서도 상관없다고 생각해보자.

즉 (A1, A2, ..., AM) 뿐만 아니라 (A2, A1, ..., AM) 등도 가능하다고 생각하자.

그러면 B를 0의 위치부터 1, 2, ... N - 1까지 하나하나 추가해 나간다고 생각하였을 때

1) i가 A에 존재하지 않는다면 반드시 지워져야 하므로 i가 MEX가 되는 구간이 필요하다.

-> 따라서 i는 기존에 이미 만들어진 (0, 1, .. i - 1)의 배열의 왼쪽 끝이나 오른쪽 끝에만 붙어야 한다.

2) i가 A에 존재한다면 i MEX가 되는 구간이 있든지 없던지 별로 상관이 없다.

-> i는 중간 아무데나 끼어들어도 상관 없다.

 

이제 순서를 고려해보자.

위를 보면 (0, 1, 2, ... i - 1)이 붙어서 존재한다.

그러면 이때 제일 왼쪽의 위치를 L, 제일 오른쪽의 위치를 R이라고 하자.

다시 말해, 제일 왼쪽은 A[L]보다 왼쪽에 존재하고, 제일 오른쪽은 A[R - 1]보다 오른쪽에 존재한다

예를 들어 A = {1}이라면 {0, 1, 2}라는 배열은 L = 0, R = 1이 될 것이다.

그러면 dp[L][R] = (L이 제일 왼쪽, R이 제일 오른쪽인 경우의 수}라고 하자.

똑같이 i번을 추가할 때

1) i가 A에 존재하지 않는 다면 배열의 왼쪽 끝이나 오른쪽 끝에 붙어야 한다

-> 왼쪽에 붙는 경우 : nxt[L' <= L][R] += dp[L][R]

-> 오른쪽에 붙는 경우 : nxt[L][R' >= R] += dp[L][R]

-> 따라서 적당한 L', R'에 대해서 nxt[L'][R'] = dp[L >= L'][R] + dp[L][R <= R']의 합을 구하면 된다.

-> 위의 계산은 누적합을 통해서 할 수 있다.

2) i가 A에 x번째로 존재한다면, 반드시 그 자리에 추가되어야 한다

-> nxt[min(L, x)][max(R, x)] += dp[L][R]

-> 이건 그냥 그대로 진행하면 된다.

위의 dp는 O(N^3)으로 굴러간다.