AtCoder Regular Contest 166

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

오랜만이라고 느낀 ARC.

사실 ARC, AGC에서는 좋은 퍼포를 못 내는 편이다.

오늘은 쉴까 했는데 출제자가 maspy 정도면 괜찮지 않을까란 생각이 들어 참가했다.

일단 ABCD는 풀었고 E를 푼 인원이 15명이니까 뭐 만족하는 편이다.

D는 298솔이기에 D의 속도로 이번 ARC는 갈린 느낌

 

A. Replace C or Swap AB

 

편의상 문제에서 주어진 두 string을 S, T라고 하겠다.

만일 T[i] = 'C'라면, 반드시 S[i] = 'C'이다.

-> 당연히 operation 1, 2에 의해서 C를 A, B로 바꾸는 것은 가능하지만, 그 역방향은 안되기 때문이다.

 

이제 operation 3를 고려해주어야 한다.

operation 3를 잘 보면 'A', 'B'로 이루어진 substring에서 'B'들을 원하는 만큼 앞으로 옮길 수 있는 기능임을 알 수 있다.

T[L] = 'C', T[R] = 'C'이고, L < i < R인 모든 i에 대해서 T[i] != 'C'인 모든 (L, R) 범위가 S = T 변환이 가능한지 확인하면 된다.

'B'는 앞으로 옮길 수 있으므로 모든 S[i] = 'C'인 애들에 대해서 앞쪽은 전부 'A'로, 뒤쪽은 전부 'B'로 바꾸는게 최선이다.

1) 우선 [L, R]의 'C'를 모두 'A'로 바꾸거나 'B'로 바꾸어도 'A' 혹은 'B'의 개수가 부족하면 불가능

2) 모든 i에 대해 ( T에서 (L, i]에 있는 'A'의 개수) <= ( S에서 (L, i]에 있는 'A'의 개수 )임을 확인해주기만 하면 된다.

 

B. Make Multiples

 

대충 비트마스킹으로 상태를 표현해주면 된다. 

여러 방식이 존재할 것이고, 내 방식보다는 editorial의 방식이 더 좋다.

상태 j = 1 * (a의 배수인가) + 2 * (b의 배수인가) + 4 * (c의 배수인가)

dp[i][j] = (i번까지 j의 상태를 만족하게 하는데 필요한 비용)

-> 각 A[i]에 대해서, a, b, c, lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)의 배수가 되도록 해보고 dp 계산

 

C. LU/RD Marking

 

색칠하는 operation은 모든 사각형을 LD/RU의 두 삼각형으로 쪼개고, 적당히 삼각형들을 고르는 것이라 생각할 수 있다.

이때 같은 사각형에 속하지 않은 두 이웃한 삼각형은 동시에 칠해질 수 없다. (변을 공유하므로 당연하다)

claim) (문제에서 구해야 하는 number of set of edges) = (number of set of operations)

pf) 서로 다른 두 operation의 집합 S, T가 똑같은 결과물을 도출한다고 가정해보자

-> 당연히 어떤 operation x가 존재하여 S에는 있는데 T에는 없을 것이다.

-> 그러면 x가 색칠하는 두 변을 채우기 위해서 T에서는 x과 이웃한 두 삼각형 y, z이 반드시 칠해져야 한다.

-> 그러면 S는 y, z가 없으니 또 이와 이웃한 y', z'이 칠해진다

-> (반복...) -> 마지막에는 경계에 도달하기 때문에 없는 색칠을 보상해줄 삼각형이 없어 같을 수 없다.

 

일반성을 잃지 않고 H <= W라고 가정하자.

색칠의 형태를 보면 H * W 사각형을 서로 영향을 끼치지 않는 H + W개의 composition으로 나눌 수 있음을 알 수 있다.

-> 서로 이웃한 삼각형들끼리만 영향을 주기 때문에 이들을 이으면 한 줄로 이루어진 삼각형들이 있음을 알 수 있다.

-> i개의 삼각형으로 이루어진 composition을 칠하는 방법을 F[i]라고 하자.

-> composition들 각각에 대한 방법수의 곱인 F[1] * F[3] * ... F[2H - 1] * F[2H] * ... F[2H] * F[2H - 1] * ... F[3] * F[1]이 답.

-> 미리 모든 1e6까지의 수에 대해서 G[x] = F[1] * ... F[2x - 1]을 계산해두고, modpow(F[2H], W - H)를 때리면 됨

 

F를 구해야 한다.

x번 삼각형을 칠하기 위해선 x - 1번이 칠해지지 않아야 함

-> F[x] = F[x - 2] + ... + F[1] + F[0]의 점화식이 성립한다.

-> F[x - 1] = F[x - 3] + .. + F[0]이므로, 위의 점화식에 대입하면 F[x] = F[x - 1] + F[x - 2]

 

D. Interval Counts

 

편의를 위해서 x[0] = -INF, x[n + 1] = +INF라 하자.

또한 (L, R) 쌍을 [L, R]의 대괄호를 열고 닫는 방식으로 여긴다. 즉, L에서 괄호를 열고, R에서 괄호를 닫는다.

만일 i번을 포함하지 않도록 괄호를 열고 싶다면 x[i] + 1에서, 닫고 싶다면 x[i] - 1에서.

만일 i번을 포함하도록 괄호를 열고싶다면 x[i - 1] + 1에서, 닫고 싶다면 x[i + 1] - 1에서.

-> L, R의 위치를 선정하는데에는 위의 규칙을 반드시 따른다.

-> 또한 모든 L들의 위치와 모든 R들의 위치가 결정되면 L[i] <= L[i + 1], R[i] <= R[i + 1]을 만족해야 한다.

 

claim) 괄호를 열 수 있는 만큼 최대한 괄호를 열고, 괄호를 닫는 것은 최대한 미루는게 언제나 제일 이득이다.

-> 예를 들어, 현재 열려 있는 괄호의 개수가 j개라고 하자.

-> y[i] > j라면, x[i - 1] + 1에서 괄호를 y[i] - j개만큼 연다

-> y[i] < j라면 x[i] - 1에서 괄호를 j - y[i]개만큼 닫는다.

-> claim에 의하면, y[i] < j일 때, 굳이 x[i] - 1에서 괄호를 j - y[i] + x개를 닫고, x[i - 1] + 1에서 x개를 열 필요가 없음

pf) L[i]가 '굳이 열린 괄호'이고 R[j]가 '굳이 닫힌 괄호'이며 이들이 존재한다고 가정하자.

만일 i < j라면 L[i] 이전에 열린 괄호가 R[j] 이전에 닫힌 괄호보다 적단 건데, 이러면 열린 것보다 닫힌게 많아 말이 안됨.

i >= j이고, 이로 인해 R[i] >= R[j]이다

R[i]와 R[j]를 swap해주자. (R'[i] = R[j], R'[j] = R[i])

-> swap 받더라도 모든 원소를 괄호에 포함하는 횟수는 동일하기에 상관 없다.

-> 이제 (L[i], R'[i] = R[j]) 쌍은 어떤 원소도 포함하지 않는 괄호이므로 그냥 제거해주자.

그러면 (L1, L2, ... L[i - 1], L[i + 1], ...)와  (R1, R2, ... R[i - 1], R[i + 1], ...)가 생기고, 새로운 min 값은 기존의 이상이다.

-> 1) j만 R값이 증가한 것인데, R값이 증가만 한 상황에서 당연히 바뀐 답은 기존의 이상이다

-> 2) (R[i] - L[i])가 제거되었고, 숫자가 제거되었으니 바뀐 min 값은 기존의 이상이다

따라서 모든 '굳이 열리고 닫힌 괄호'는 모두 제거해도 답이 감소하지 않으므로, 그냥 없는 상황이 제일 이득이다.

 

세줄요약하자면

1) 괄호는 열 때 최대한 왼쪽에서 열고 닫을 때 최대한 오른쪽에서 닫는다

2) 현재 열린 괄호의 수가 y[i]보다 크면 괄호를 닫고, 현재 열린 괄호의 수가 y[i]보다 작으면 괄호를 연다

3) 괄호 쌍을 지을 때는 L1 < L2 < ... < Lk, R1 < R2 < .... < Rk가 되도록 배정한다.

 

E. Fizz Buzz Difference

 

어떤 (L, R) 쌍이 있다고 가정하자.

[L, R] 범위에 대해서 a의 개수를 최대한 줄이고, b의 개수는 최대한 늘리고 싶다.

-> L - 1과 R + 1이  a의 배수이면 참 좋겠다는 생각이 든다.

-> 만일 만족하지 않는다면, 단순히 L - 1, R + 1이 a의 배수일 때까지 각각 감소, 증가시키면 된다.

-> 어차피 na는 증가하지 않을 것이고 nb는 증가하면 이득이니까 이 행동은 무조건 이득이다.

-> \(L = al + 1, R = ar - 1, n_a = r - l - 1\)

 

\(n_b = R / b - (L - 1) / b = (ar - 1) / b - (al) / b\)   (단, 여기서 \(x / y = [ x / y ]\) )

\(al = bp + q\) 라고 가정할 수 있고, \(ar = (n_a + 1) * a + bp + q\) 이므로 \(n_b = (q + (n_a + 1) * a - 1) / b\) 

우리는 nb를 최대한 키우고 싶기 때문에 q를 최대한 키우고 싶고 q = b - gcd(a, b)를 만족한다.

-> \(na - (b - gcd + (n_a + 1) * a - 1) / b = n\) 이고, 제일큰 n_a를 선택하면 어련히 R - L은 커진다.

//여기까지는 할만하지 않나 싶다.

//사실 대회도중에는 여러가지 a, b를 테스트하면서 [L, R]의 규칙을 찾는 방식으로 시도했었다.

 

근데 문제점은 L이 최소가 되어야 한다는 점이다.

-> al = bp + q인데, q는 위에서 b - gcd(a, b)가 되었을 때의 값과 같은 값을 반드시 주어야 한다.

-> al % p = q >= y인 최소의 l를 구해주어야 하는 것이다.

이쯤에서 a, b는 서로소라고 가정하자. (만일 아니라면, 마지막에 a/d, b/d로 풀고 마지막에 Ld - d + 1, Rd + d - 1로)

-> al = q (mod b) -> l = q * inva (mod b)를 만족하며, q는 (y, y + 1, .. b - 1) 중 하나

-> q = (b - 1) - r이라고 여기면 r는 (0, 1, .. b -y - 1)중 하나이고 r * (-inva) - inva (mod b)를 구하면 된다.

https://maspypy.com/library-checker-min-of-mod-of-linear 의 라이브러리를 사용하면 구할 수 있다.

 

쓰읍.... 이건 좀 너무 빡센게 아닌가....