Codeforces Global Round 25

https://codeforces.com/contest/1951

 

E가 1241솔인데 F가 244.

난이도 절벽이 있었고, 나는 F를 못 풀었다.

간만에 div1을 쳐서 점수 하락을 크게 걱정했는데, 이정도면 뭐...

 

A. Dual Trigger

 

당연히 켜진 램프가 홀수 개면 불가능

그리고 켜진게 2개이고 서로 붙어있다면 불가능하다.

이외의 경우에는 i, i + cnt / 2 번째를 동시에 켜면 된다.

 

B. Battle Cows

 

기본적인 아이디어는 K번 cow를 모든 i번자리와 swap해보는 것.

다음과 같이 b와 c를 정의하자

b[i] = max(a[0], a[1], ... a[i - 1])

c[i] = j가 성립한다면, a[k] >= a[i] && a[k] >= a[i + 1] ... && a[k] >= a[i + j - 1] && (i + j == n || a[k] < a[i + j])

 

case 1) b[i] > a[k]라면, i번 자리에 가져다 놓더라도, i - 1번까지의 결과물에게 바로 져버리기에 0

case 2) a[i] > a[k] && k > i라면, i번 자리에 가져다 놓았을 때 min(k - i - 1, c[i + 1] - i - 1) + !!i

-> 왜냐하면 i번 자리부터 고려했을 때 c[i + 1] - i - 1 + !!i번 이길 수 있지만, 결국 k번 자리의 a[i]한테는 진다

case 3) 나머지의 경우 c[i + 1] - i - 1 + !!i

 

대회가 끝나고 나서 생각해보니, b[i] <= a[k]라는 조건이 터지려면 내 앞에 a[x] > a[k]인 x가 없어야 한다.

따라서 그냥 0번째 자리, 1번째 자리, 나보다 큰 첫 번째 자리로 가야 한다.

 

C. Ticket Hoarding

 

일단 제일 티켓이 제일 싼 날짜들에서 구매를 할 것임은 당연하다.

이제는 티켓을 어떤 방식으로 구매하는 것이 제일 싼 방식인지만 결정하면 된다.

예를 들어 (1, 1, 1, 1, 1)의 방식으로 사는 것보다는 한 번에 5장을 사는게 당연히 제일 좋다.

조금 더 고민해보면 (m, m, m, m, ... m, k % m, 0, 0, ... 0, 0)로 구매하는 것이 제일 이득이다.

 

증명해볼 필요도 없이 자명한 편인데 증명을 해보도록 해보자.

어떤 b에 대해서 b[0] + b[1] + ... b[n - 1] = k, b[i] <= m이 성립할 때 b[0] * 0 + b[0] * b[1] + ...의 최솟값을 구하자.

b[0] + .. b[n - 1] = k가 성립하므로 sum(b[i]^2) + sum(2 * b[i] * b[j]) = k^2이 성립한다.

따라서 sum(b[i]^2)을 최소화 시켜주어야 하고, 각 b[x]를 최대화 시켜주는 것이 이득이다.

 

D. Buying Jewels

 

그냥 jewel 2개로 땡친다고 생각하는데 2번째 jewel은 1원으로 처리하자.

1) N = K일때 : 1원으로 하나 팔면 끝

2) K <= (N + 1) / 2일때 : N - K + 1원에 1개 팔고, 나머지 K - 1개를 1원으로 팔면 끝

3) 나머지는 불가능하다

-> pf) 첫 jewel을 1원에 팔면 무조건 N개가 나가버리기에 2원 이상이므로, 최대 N % 2 + N / 2개만 팔 수 있기 때문이다.

-> 따라서 어떻게 팔더라도 N개 미만 팔 때 (N + 1) / 2개를 넘게 팔 수 없다.

 

E. No Palindromes

 

claim) 어떤 string을 non-palindrome으로 쪼개는게 가능하다면 반드시 1개 혹은 2개로 쪼개진다

귀류법) non-palindrome으로 쪼개는 최소 개수가 K > 2라고 가정하자.

순서대로 S[0], S[1], ... S[K - 1]이라고 하고, 이 중에서 제일 길이가 짧은 것은 i번이라고 하자.

K는 최소이므로, (S[p] + S[p + 1] + ... S[i])나 (S[i] + S[i + 1] + .. + S[q])는 반드시 palindrome이다.

1) i가 0이나 N - 1이 아닌 경우

-> S[0],... S[i -1]은 invS[i]로 시작하고, S[i + 1], ... S[K - 1]은 반드시 invS[i]로 끝난다.

-> S[i]는 palindrome이 아니므로 (S[0] + ... S[K - 1])은 palindrome이 될 수 없다.

2) i가 0인 경우 (N - 1이면 그냥 뒤집으면 되니 똑같다)

-> (S[1] + S[2])는 palindrome이므로 S[2]는 invS[1]으로 끝난다

-> (S[0] + S[1] + S[2])는 palindrome이므로 S[0]는 S[1]으로 시작한다.

-> (S[0] + S[1])은 palindrome이므로 S[1]은 invS[1]으로 끝난다.

-> 따라서 S[1]이 palindrome이 되어버리고 모순

 

이후에는 [0, i], [i + 1, n - 1]로 쪼개는게 가능한지만 체크하면 되기 때문에 Z algorithm을 써서 해주면 된다.

사실 케이스워크만으로도 할 수 있다.

 

F. Inversion Composition

 

대충 몇 번 굴려보면 inv(p) <= inv(q) + inv(q * p) <= n * (n - 1) - inv(p)가 성립함을 알 수 있다.

즉, inv(q) + inv(q * p)개가 inv(p)개 아래로 내려올 수도 없고, inv(p)가 일종의 상방으로도 작용한다.

그러면 p에서 inverse가 되는, i < j인데 p[i] > p[j]인 (i, j) 쌍을 잠시 들여다 보자.

이때 inv(q)에서 (p[j] < p[i])쌍으로, inv(q * p)에서 (i, j)쌍으로 들어갔을 때 inverse인지 여부가 반드시 다르다.

즉, 이런 (i, j) 쌍은 inv(q) + inv(q * p)에서 정확히 1번 inverse로 나타난다는 것이다.

반대로 i < j인데 p[i] < p[j]인 (i, j)에 대해서는 q[p[i]] < q[p[j]]라면 0번, q[p[i]] > q[p[j]]라면 2번 inverse로 나타난다.

따라서 이거만 construct하면 된다.

 

일반적으로 inversion의 개수를 construct할 때는 제일 앞에서부터 하나씩 뒤로 보낸다.

그래서 우리도 비슷하게 일단은 생각할 수 있다.

그냥 하던 것과 똑같이 (i, i + 1, ... n - 1, i - 1, i -2, ... 0)로 만들었다고 생각하자 우선.

여기서 어떤 숫자를 한 칸 옮긴다고 해서 inversion 관계가 1개 증가하는게 아니라 2개씩 바뀌곤 한다.

 

그래서 증감이 적당히 유지가 되도록 관리를 해야 한다...

editorial의 construction을 참고하면 될 것 같다.

내가 inv(q) + inv(q * p) 값을 구하는 테스트 파일을 잘못 짜서 이쪽 풀이를 포기했다.

카페인을 너무 많이 먹어서 판단이 흐려졌나보다...