Codeforces Round 932 (Div. 2)
https://codeforces.com/contest/1935
부캐 오렌지 보내기를 하려고 했는데 레지를 실수로 못했다.
아마 레지만 했으면 가볍게 갔을 것 같다.
A. Entertainment in MAC
A번이라서 강한 확신이 있기에 풀이를 당시에는 증명하지 않았다.
어차피 뒤집는 작업을 통해 n은 0이나 1이 되버리고, n이 짝수로 고정되어 있으니 결과는 S나 T + S
둘 중에 더 빠른 것을 쓴다.
B. Informatics in MAC
어떤 두 그룹의 MEX가 같다면, 그 두 그룹을 합치고 나서도 MEX 값은 유지된다.
따라서 항상 k = 2라고 생각해도 상관 없다. (k > 2인 경우가 있다면, 반드시 k = 2로 쪼개는 방법이 존재한다)
따라서 단순하게 (a1, a2, .. a[i - 1]) (a[i], ... a[n])을 해보면 충분하다.
두 그룹 L, R에 대해서 L은 MEX가 항상 증가하고, R은 MEX가 항상 감소한다는 성질로 MEX를 관리할 수 있다.
물론 나처럼 생각하는게 귀찮으면 set을 잘 관리해줘도 된다.
C. Messenger in MAC
저 크게 보이는 시그마에서 아주 쉽게 다음과 같은 생각을 할 수 있다.
-> p1, p2, ... pk에 대해서 반드시 b[p1] <= b[p2] <= ... <= b[pk]가 성립한다
-> 만일 아니라면, 위와 같이 정렬함으로써 a의 합은 유지하고, 뒤쪽 b로 인한 값을 줄일 수 있다.
따라서 모든 숫자를 (b[i], a[i])로 정렬하자.
그 다음에 앞에서부터 x개를 골랐을 때의 최솟값을 구해보면 된다.
-> dp[i][j] : (dp[i][j] + a[i] + b[i]가 0부터 i - 1번까지 j - 1개를 고르고 i번을 골랐을 때의 최솟값이 되도록 하는 값)
-> 이러면 dp[i][1] = min(dp[i - 1][1], a[i] - b[i])가 되고, 이외에는 dp[i][j] = min(dp[i - 1][j], dp[i][j] + a[i])
-> 따라서 dp를 모두 순회하며 dp[i][j] + a[i] + b[i] <= l이 성립하는 최대의 j를 구해주면 된다.
D. Exam in MAC
단순한 카운팅이다.
처음에는 남은 (y - x) 각각에 대해서 가능한 순서쌍 수를 세려고 했다.
하지만 제한이 1e9로 꽤나 큰 것을 보고, 불가능한 것을 지우는 것으로 자연스레 관점이 바뀌었다.
1. 우선 총 카운팅 대상인 (y - x, x + y) 쌍의 개수는 (C + 1) * (C + 2) / 2
-> y - x = K일 때 가능한 x + y의 개수가 C + 1 - K이기 때문이다.
2. y - x = S가 되도록 하는 쌍의 개수는 위에서 설명한 것과 똑같이 C + 1 - S
3. x + y = S가 되도록 하는 쌍의 개수는 S / 2 + 1
4. y - x = S[i], x + y = S[j]가 되는 경우만 세자 (단, i와 j는 동일할 수 있다.)
-> 우선 S[i]와 S[j]는 기우성이 같아야 하므로, 기우성이 같은 S값들 끼리만 모아두고, 정렬하자.
-> S[i] <= S[j]는 당연히 성립해야 한다.
-> 그 다음에 이는 투 포인터로 셀 수 있다. (S[i + 1], S[j]) 조합이 가능하면, (S[i], S[j])도 가능하기 때문이다.
E. Distance Learning Courses in MAC
일단은 내 풀이를 살펴보자. (정해가 훨씬 이쁘므로... ㅋㅋ)
문제가 생긴 모양을 보고서 금광세그의 형태를 의심했다.
-> segtree에 int가 아니라 새로운 struct info를 정의해서 넣을 것인디 info가 무엇이 될 것인가
-> info에 나는 최선이 되는 가능한 모든 숫자들을 넣었다
-> 예를 들면 X[i] <= A <= B <= Y[i]인 (A, B)에 대해서 만일 B 안에 A가 속한다면 (A | B == B) A는 제외했다는 뜻
-> 조금 생각해보면 info의 크기는 그렇게까지 커질 수 없다.
단순히 [X[i], Y[i]]라는 범위가 주어진다면 info에는 어떤 숫자들이 들어갈까?
다음을 정의하자
-> f(x) = ((Y[i] - (1 << x)) OR ( (1 << x) - 1)) (단, Y[i]의 x번째 비트는 켜져있다.)
즉, Y[i]에서 x번째 비트를 포기하고 나머지 비트를 모두 킨다는 것이다.
예를 들어 [0, 1010100]이라면, 1010100, 1010011, 1001111, 111111 중 하나를 고를 것이다
이 숫자들만이 아까 위에서 이야기한 '최선이 되는' 숫자들이고, 그 개수는 명백히 30개 이하이다.
f값들 중에서 X보다 크거나 같은 숫자들만 관리하면 된다.
그럼 이제 두 info를 합치는 과정은 어떻게 할 것인가? (a + b)
위에서 보면 알 수 있지만, info에 들어있는 모든 숫자들은 맨 뒤에 적당히 1이 연속으로 들어가 있다.
a[x] = (a에 들어있는 원소 중 뒤에 1이 연속으로 x개 들어가 있는 원소)라고 한다면
a[x] OR b[0]가 무조건 a[x] OR b[1], a[x] OR b[2], ...a[x] OR b[x]보다 무조건 이득이 된다.
a[x] OR b[x + 1]보다는 a[0] OR b[x + 1]이 더 이득이기에 이들 또한 무시하여도 된다.
따라서 (a[i] OR b[0])와 (a[0] OR b[i]) 들만 모두 저장하면 a + b = c가 만들어진다.
하지만 이렇게 되면 항상 info의 크기가 두 배가 되지 않는가? (즉, c의 size가 a.size + b.size 아닌가?)
여기서 또다시 '최선'이 되지 않는 원소들은 모두 지워준다.
-> 이 과정을 나는 일일이 (info 크기) ^ 2의 시간을 들였기에 합치는데 시간이 오래걸린다.
-> 또한 여전히 c의 원소들은 뒤에서가 1로 연속하기 때문에 개수가 30개 이하임이 유지된다.
-> 끝에 1의 개수가 동일한 A, B가 모두 살아남았다고 가정하자 (단, A > B)
-> 그러면 A의 두 번째로 큰 비트 second에 대해 second를 포기하고, 그 뒤로 전부 1인 원소가 C가 존재한다.
-> C는 B보다 무조건 우위에 있기 때문에, B가 살아남았음에 모순
사실 꽤 느려질 수 있다고 걱정했는데 프리텟에서 1.3초가 나오기에 그냥 안심했다.
정해를 살펴보자. 에디토리얼 상태가 살짝 안 좋아서 내 나름의 해석을 했다.
우선 common_prefix(X[i], Y[i])는 항상 i가 범위에 들어가는 [L, R]에 대해 켜지게 된다.
따라서 common_prefix(X[i], Y[i]) = W[i]라고 하고, X[i] - W[i] = X'[i], Y[i] - W[i] = Y'[i]
-> [L, R]에 대한 답은 (W[L] OR W[L + 1] OR ... OR W[R]) OR (X'과 Y'들을 통한 답)이 된다.
-> segtree 등을 이용해서 W[L]부터 W[R]까지 모두 OR을 취한 값을 구할 수 있다.
이제 그러면 X', Y'을 통한 답을 구할 차례이다.
그렇다면 [X', Y']에서 선택하는 숫자는 항상 : Y[i]거나 Y[i]에서 비트를 하나 포기하고 연속된 1을 얻은 숫자이다
예를 들어 [0, 1010100]이라면, 1010100, 1010011, 1001111, 111111 중 하나를 고를 것이다
근데 우리가 이미 알고 있듯이 X'과 Y'은 항상 첫 번째 비트가 다르다! (common prefix를 제거했으므로)
즉, Y'에 대해 하나의 비트를 포기한 모든 숫자는 이미 X'보다 크거나 같다.
따라서 우리는 그냥 X' = 0이라고 생각해도 상관이 없다.
X'이 0일 때에는 다음과 같이 문제를 풀 수 있다.
우린 그리디하게 제일 큰 비트부터 답에 포함시키는 과정을 생각할 수 있다.
어떤 i번째 비트가 [L, R] 범위 내의 Y'에서 C번 등장한다면
-> C = 0 : 이 비트는 켜질 수 없음
-> C = 1 : 이 비트는 그냥 키면 됨
-> C >= 2 : 적당히 i번 비트가 켜진 Y'[a], Y'[b]에 대해서, Y'[a]는 그냥 취하고, Y'[b]는 i번 비트를 포기하여 선택
-> 그렇다면, i번 비트부턴 모든 비트가 켜지게 되므로, 이게 항상 제일 이득이고 break
각 비트에 대한 prefix sum을 관리하면 모든 [L, R] 범위에 i번째 비트의 개수인 C를 O(1)로 구할 수 있다.
따라서 복잡도는 (미리 W 구해두기) + Q * ((segtree로 W의 OR구하기) + (그리디하게 계산)) = O(30 * (N + Q)) 정도
F. Andrey's Tree
상당히 흥미로운 문제이다...
dfs를 잘 긁거나 s2l 잘 쓰면 될 것 같은디...