AtCoder Regular Contest 159

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

 

사실 퍼포가 잘 나와서 문제가 좋았는지 나빴는지 객관적인 평가를 못 내리겠다

앳코더는 점수가 찔끔찔끔 바뀌는게 참 감질맛 나는 것 같다

뭐 2400점이 블루 1800퍼포를 해도 -48인거면 어떤 의미로는 좋을지도 모르겠다.

또한 앳코더는 패널티가 상당히 뼈아프게 들어간다는 것을 기억하여야 한다.

 

A. Copy and Paste graph

 

x[i][j] = x[i % n][j % n]이므로 플로이드 와샬을 돌리면 된다.

 

B. GCD subtraction

 

A, B가 있다고 하자.

어차피 두 개가 d의 배수라면 A/d, B/d로 해도 똑같은 횟수를 하기에 __gcd(A, B) = 1이라고 가정해도 된다.

그러면 gcd(A-x, B-x)가 1이 아니도록 하는 제일 작은 x를 찾아주면 된다.

이때 x는 a - b의 배수이므로 a - b의 모든 소인수 p에 대하여 (A-x, B-x)가 p의 배수가 되는 제일 작은 x를 구하면 된다.

그러면 한 번 할 때마다 p씩 줄어들고 매번 a-b보다 작은 모든 소수를 확인해야 하니 대략 O(lgMAXA * sqrt(MAXA))이다.

 

C. Permutation Addition

 

당연하게도 a1 + ... + an + n * (n + 1) / 2가 n의 배수가 되는 것이 불가능하면 No이다.

만약에 No가 아닌데 a1 + .. + an이 n의 배수가 아니면 편의사 (1, 2, .. n)을 더해주어 n의 배수로 만들어주자.

 

모든 숫자들을 같게 만드는 것이 목표이므로 제일 큰 것에서 빼고, 제일 작은 것에서 더하는 것을 생각하자.

매번 제일 큰 애와 작은 애를 골라서 필요한 만큼 더하고 빼주면 된다.

이제 이 operation을 permuation으로 구하면 된다.

WLOG a1이 제일 작고 a2가 제일 크다고 하자. 만일 1을 더하고 1을 빼주고 싶다면

(1, 2, ... n - 1, n), (n, n -1, ... 2, 1)을 더하면 모든 숫자에 같은 값이 더해지겠지만

(2, 1, 3..., n - 1, n), (n, n - 1, ... , 2, 1)을 더하면 a1에는 비교적 1이 더 더해지고 a2에는 1이 덜 더해진다.

만일 1이 아닌 다른 숫자를 더하고 싶다면 1, 2를 swap하는 대신 1, x를 swap해주면 된다.

 

D. LIS2

 

웬일로 딱 자료구조 문제가 나와주었다.

dp[x] = (x 이하의 숫자를 끝으로 하는 LIS의 최대길이)

[L, R]이 들어간다면 [0, L)에서 dp의 최댓값 ret을 구하고 [L, R]에 대해서 dp[x] = max(dp[x], ret + x - L + 1)

등차수열 비슷한 것을 max 시켜주는 lazy segtree를 만들어주면 된다.

 

하지만 segtree를 안 쓰는 방법도 있다.

map<int, int> m에 대해서 m[x] = y라면 구간 [m[x], y)에 대해서 dp의 값이 1씩 더 커진다고 생각하자.

그렇다면 맨 마지막에 모든 m[x] = y에 대해서 y - x의 합을 구해주면 답이 될 것이다.

 

1. 새롭게 [L, R]이 들어간다고 생각해보자.

    만약에 [L, R]과 앞쪽에서 겹치는 구간 [L', R']이 있다면 [R' + 1, R]이 들어간다고 생각해도 된다.

2. 만약에 뒤에 [L', R']이 있는데 R - L보다 작은 구간이 있다면, 어차피 [L, R]로 갱신된 값이 더 크다.

    따라서 그 구간은 지워도 된다.

3. 이제 더 이상 dp값이 더 작은게 없다고 하자. 그 뒤에 [L', R']이 있다면

    남은 size만큼 L'에 더해서 [L' + size, R']으로 바꿔주고 [L, R]을 넣어주자.

https://atcoder.jp/contests/arc159/submissions/40444377

 

F. Good division

 

일단 E는 도대체 이 operation이 무엇을 의미하는지 이해하기 어려워서 포기했다.

그 다음에 F를 봤다.

일단 Good sequence가 어떤 sequence인지는 명확하다 : [L, R)에 대해 특정 숫자의 개수가 (R-L)/2를 넘지 않으면 된다.

 

그러면 O(N^2)이라고 생각하면 매우 단순하게 풀 수 있다.

dp[x] = (x개를 good하게 나누는 방법의 수)라면

dp[x] = dp[x - 2] * (2개 가능) + dp[x - 4] * (4개 가능) + ...을 해주면 된다.

근데 도대체 이걸 어떻게 해야 O(NlgN), 혹은 5e5니까 O(N)으로 할 수 있는가?

 

일단 에디토리얼의 O(N^2) 풀이를 보자.

에디토리얼에서 good한지를 판단하는 방법은 다음과 같다.

-> f[v][i] = (a[2i], a[2i + 1]에서  v의 개수) - 1

-> 이때 [2* L, 2* R + 1]이 good하려면 모든 v에 대해서 f[v][L] + ... f[v][R]이 0 이하여야 한다.

그러면 memo[v][i]를 다음과 같이 정의하자

-> memo[v][i] = sum(dp[j]) : 단, f[v][0] + .. + f[v][j] = i인 j만

그러면 이제 dp[i]를 구하자

-> tmp[v][i] = sum(memo[v][j]) : 단,  f[v][0] + .. + f[v][i] < j인 j만

어떤 구간은 당연히 단 하나의 숫자 v에 대해서만 불가능하다. (절반이 넘는게 2개 이상일 수 없다)

-> 그러면 sum(tmp[v][i])값이 불가능한 dp값이 되고 전체 dp[0] + .. dp[i - 1]까지 더하고 빼주면 된다.

https://atcoder.jp/contests/arc159/submissions/40496764

 

여기서 실제로 memo와 dp의 변화에 관여하는 값들을 생각해보자.

어떤 v, i에 대해서 dp[i]가 나중에 v값 때문에 dp[j]에 관여하지 못한다고 생각하자.

그렇다면 f[v][i] + .. + f[v][j] >= 0이라는 뜻이다.

위를 만족하는 모든 (v, i) 순서쌍의 개수는 O(n)이다.

간단하게 생각하면 어떤 v에 대해 v가 majority가 되는 구간에 있는 (a[2i], a[2i+1]) 모두 v가 아닌 i의 개수가

(a[2k], a[2k+1])이 모두 v인 k의 개수랑 비슷하다.

따라서 이런 변화가 유도되는 (v, i)의 개수가 얼마 안되므로 이들에 대해서만 확인해주면 O(N)

값처리에 정렬이나 map을 쓰면 O(NlgN)인데 생각보다 상수가 크니 조심

https://atcoder.jp/contests/arc159/submissions/40526653

 

E. Difference Sum Query

몰루