Codeforces Round 884 (Div. 1 + Div. 2)
레드가 되었습니다.
사실 예전에도 GM이 된 적이 있는데, 중국인들의 대거 치팅으로 언레당해서 지금이 첫 레드가 달성이 되었다.
근데 2385가 2700의 퍼포를 보였는데 +84라니... 짜게 느껴진다.
F1을 꽤나 빨리 푼 관계로, 늦은 F1 + F2인 사람들의 일부보다 점수가 높게 찍혔다.
A. Subtraction Game
a + b.
진짜 이게 끝인지 5번 정도 머리속에서 검토하고 제출했다.
B. Permutations & Primes
제일 먼저 생각할 수 있는것은, 최대한 많은 구간에 1을 포함시켜야 한다는 것이다.
1이 포함되지 않으면 Mex = 1이 되어서 소수가 안되기 때문이다.
이러면 1을 중앙에 박고 생각할 수 있다.
1만 포함한 구간은 Mex = 2로 소수이기에, 이제는 2를 최대한 포함시키지 않으려고 할 수 있다.
이러면 2는 제일 왼쪽 끝에 박으면 된다.
1과 2를 포함한 구간은 3만 없으면 Mex = 3로 소수이다.
그러면 이제 3을 제일 오른쪽 끝에 박으면 된다.
C. Particles
마지막에 남는 particle은 여러 particle의 합이라고 생각할 수 있고, 이 particle들의 집합을 S = {c[i], c[j], .. }이라고 하자.
이때 S에 남는 particle들은 반드시 index의 기우성이 같다.
-> 왜냐하면 index의 기우성이 다른 두 숫자는 서로 충돌시키는 것이 불가능하기 때문이다.
따라서 DP를 이용하여
dp[i] = (i번을 포함한, i와 기우성이 같은 subset을 골랐을 때의 합의 최댓값)을 구하면 된다
-> 이건 간단하게 dp[i] = Max(dp[i - 2k]) + c[i]가 되므로 Max(홀수들), Max(짝수들)만 잘 관리하면 구할 수 있다.
cf) 사실 추가로 위의 방식으로 고른 particle 집합을 실제로 마지막에 남길 수 있음을 증명해야 한다.
-> 그냥 앞에서부터 사라져야 하는 particle들을 제거하면 쉽게 S를 남길 수 있다.
D. Row Major
문제의 조건은 다음과 같이 요약할 수 있다.
N의 모든 약수 d에 대해서 A[x] != A[x + d]를 만족한다.
따라서 N의 약수가 아닌 최소 숫자 K를 잡으면 1, 2, 3, ... K, 1, 2, 3...로 색칠해주면 간단하게 조건을 만족시킬 수 있다.
cf) 사실 어느 정도 자명하다만, 1, 2, ... d가 모두 N의 약수면 d는 당연히 불가능하다.
-> 1, 2, .. d, d + 1이 모두 색이 달라야 하기 때문.
E. Great Grids
우선 첫 행과 첫 열이 결정되면 모든 grid가 결정됨을 확인할 수 있다.
첫 열을 s[0] ~ s[n - 1], 첫 행을 t[0] ~ t[m - 1]이라고 한다면
(x, y) = (s[x] + t[y]) % 3이다.
그렇다면 (x1, y1) == (x2, y2)라는 뜻은 s[x1] + t[y1] == s[x2] + t[y2]라는 의미이고, s[x1] - s[x2] == t[y2] - t[y1]이다.
편의를 위해 x1 < x2라 잡으면, 문제 조건에 의해 x2 = x1 + 1이다.
1) y1 = y2 + 1 : s[x1] - s[x1 + 1] == t[y1] - t[y2 + 1]
2) y2 = y1 + 1 : s[x1] - s[x1 + 1] == t[y1 + 1] - t[y1]
-> 따라서 대략 (s[x + 1] - s[x]), (t[y + 1] - t[y])간의 관계가 만들어짐을 알 수 있다.
이제 이분그래프를 만들고 나서, 인접합 두 칸은 동일 색이 아니므로, 2색 색칠이 가능한지 확인하면 된다.
-> 이건 DFS나 DSU를 이용하여 확인할 수 있다.
F1. Min Cost Permutation (Easy Version)
어차피 이걸 풀 당시에는 딱히 증명 없이 했으므로, 증명 없이 기술
c가 적당히 작은 양수라고 생각해보자.
그러면, 그냥 a를 크기순으로 정렬하는 것이 최솟값을 가져다 준다.
이번에는 반대로 c가 적당히 큰 음수라고 생각해보자.
그러면, 이번에는 a를 역순으로 정렬하는 것이 최솟값을 가져다 준다.
이것이 이 풀이의 기반이 되는 직관이다.
그러면 어떤 숫자 x가 제일 앞으로 왔다고 가정하자.
그러면 직관적으로, 뒤에 오는 숫자들은 무조건 앞으로 정렬되거나, 뒤로 정렬되었을 때 최솟값을 줄 것이다.
이때 미리 정렬된 a에 대한 계산값을 구해둔다면, O(1)으로 a[i]가 제일 앞으로 왔을 때의 최솟값을 알 수 있다.
((a[0] - b.back() - c), (a[i + 1] - a[i] - c), (a[i] - a[i - 1] - c) 제거 (a[i + 1] - a[i - 1] - c), (a[0] - a[i] - c), (a[i] - b.back() - c) 생성)
따라서 매번 남아있는 n개의 숫자들에 대해서, 최솟값을 주는 제일 작은 x를 O(n)으로 구할 수 있다.
N개의 자리에 대해서 이를 모두 진행하면 O(N^2)으로 Lexicographically smallest permutation을 구할 수 있다.
사실 만약에 c > 0이라면, 그냥 a를 정렬만 한 것이 그대로 Lexicographically smallest라서 그대로 제출하면 된다.
F2. Min Cost Permuation (Hard Version)
(a[0] - b.back() - c), (a[i + 1] - a[i] - c), (a[i] - a[i - 1] - c), (a[i + 1] - a[i - 1] - c), (a[0] - a[i] - c), (a[i] - b.back() - c)가 필요하다.
따라서 대회중에는 위의 값들의 절댓값의 합을 잘 관리해주는 segtree를 만들려고 했다.
해보려고 했는데 매우 복잡해서 포기.
Friends Standings에서 고수들을 보니까 F2를 F1을 푼 뒤 매우 빠르게 맞추는 모습이 보였다.
이래서 사실 F1에서 F2로 넘어가는, 간단한 직관이 있을 것이라고 예상할 수는 있었다.
Editorial을 좀 훑어봤는데, 아무래도 이 문제를 엄밀하게 푸는 것은 내 능력 밖인 것 같다.