CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

https://codeforces.com/contest/1896

미친 스피드포스

사람들 E, F 왜 이렇게 잘 품?

 

A. Jagged Swaps

 

문제 읽자마자 사실 풀이를 생각해냈다.

첫자리가 1이 아니면 당연히 불가능하다. 그리고 나머지는 큰 거부터 제일 뒤로 보내면 된다.

근데 괜히 너무 풀이가 쉽다 생각해서 꼬아 생각했다가 오히려 1WA 적립함...

여기부터 벌써 꼬임

 

B. AB Flipping

 

제일 앞에 있던 A를 제일 뒤에 있는 B의 위치까지 옮길 수 있다.

따라서 그 범위만큼의 자리에서 모두 flip이 가능함

 

C. Matching Arrays

 

편의를 위해 a, b가 정렬되어 있다 생각하자.

제일 좋은 방법은 (b[n - x], b[n - x + 1], ... b[n - 1], b[0], b[1], ...) 순서대로 정렬해두는 것이다.

증명하긴 좀 애매함...

 

D. Ones and Twos

 

관찰) 1 하나만 있다면, 그 주변으로 웬만한 숫자는 모두 만들 수 있다.

-> 예를 들어 1 뒤에 2 2 2 2 ...이 있다고 가정해보자

-> 2 2 2... 만으로는 짝수들밖에 못 만들지만, 1이 추가됨으로써 모든 숫자를 다 만들 수 있다.

-> 따라서 1 뒤 또는 앞에 합이 S만큼인 숫자들이 있으면, 1부터 S + 1까지는 전부 만들 수 있다.

 

S를 제일 키울 수 있는 방법이 뭐가 있을까? -> 맨 앞이나 맨 뒤의 1을 선택해주면 된다.

2 2 2 1 .... 1 2 2 2 의 형식이라고 가정하자. (앞에는 F개의 2이, 뒤에는 B개의 2가 있다고 하자)

그러면 우선 위의 관찰로 인해 tot - 2F까지의 모든 수와 tot - 2k꼴의 수를 모두 만들 수 있다.

그러면 tot - 2F부터 tot 사이에 있는 모든 tot와 기우성이 다른 숫자는 어떻게 만들 수 있을까?

-> 기우성이 바뀌어야 하므로 맨 뒤의 1을 반드시 제거해주어야 하고, tot - 2B - 1까지 만들 수 있게 된다.

 

따라서 tot - 2*min(F, B) - 1까지의 모든 숫자와, 그 이상의 tot - 2k꼴 숫자를 만들 수 있다.

 

E. Permutation Sorting

 

내 풀이)

각 숫자의 현재 위치를 inv[i]라고 하자.

관찰) inv[i] <= inv[j] <= j <= i 가 성립하는 모든 j에 대해서, j는 i보다 먼저 제자리를 찾아간다.

-> 따라서 어떤 숫자 x가 제자리를 찾아가는데 필요한 횟수는 (단순히 x까지 이동 횟수) - (먼저 제자리로 가는 개수)

-> 제자리로 가는 개수를 적당히 따져주면 되는데, 이를 셀 때 적당한 자료구조(BIT, Segtree, Pbds...)를 쓰면 된다.

-> 나는 무려 3개의 pb_ds를 이용하여 셌다...

    1) inv[i] <= inv[j] <= j <= i인 j를 세줄 pb_ds

    2) i < inv[i]가 성립할 때, inv[i] <= j인 동시에 j <= i인 j를 세줄 pb_ds

    3) i < inv[i]가 성립할 때, inv[i] <= inv[j] <= j인 j를 세줄 pb_ds

 

정해)

저딴식으로 셀 필요 없다.

무조건 inv[i] <= i라고 치자.

이걸 해결하는 방법은 만일 inv[i] > i가 성립한다면, i로 이동시키는게 아니라 N + i로 이동시킨다고 생각할 수 있다.

이렇게 모두 수정해 주면, inv[i] -> f[i]로 이동하는 셈인데, inv[i] <= inv[j] <= f[j] <= f[i]인 j의 개수를 세면 된다.

정렬해서 세든, 이차원 세그를 쓰든 잘하면 된다.

 

F. Bracket Xoring

 

일단 대놓고 불가능한 경우를 좀 걸러주자

type 1) 맨 앞과 맨 뒤는 항상 1번씩 flip되므로 s[0]과 s.back()이 다르면 -1

type 2) 항상 짝수번의 flip이 이루어지기 때문에 1의 개수가 홀수라면 -1

 

관찰1) Bracket으로 적당히 만들어진 prefix sum에 대해서 다음과 같이 flip되는지 확인 가능하다

-> 현재 위치가 '('일 경우 prefix sum의 횟수만큼 flip이 이루어진다.

-> 현재 위치가 ')'일 경우 prefix sum + 1의 횟수만큼 flip이 이루어진다.

하지만 이 관찰은 현재 위치가 '('인지 ')'인지에 따라서 바뀌기에 좀 불편하다.

 

관찰2) i번 bracket과 i + 1번 bracket이 동일하다면, 이 둘에는 서로 다른 flip 횟수가 가해진다.

-> 즉 기존에 s[i] == s[i + 1]인데 ((가 i번, i + 1번 bracket이면 이후에는 s[i] != s[i + 1]이 된다.

관찰 2를 통해 다음의 operation이 가능하다

-> s[2k] != s[2k + 1]일 경우 적당히 "(("나 "))"를 배정하고, s[2k] = s[2k + 1]이면 "()"를 배정한다.

-> 이런식으로 operation을 한번 돌리면, 모든 k에 대해 s[2k] = s[2k + 1]이 되도록 할 수 있다.

 

이제 마지막으로 모두 0으로 바꿀 타이밍이다.

-> 만약에 s[2k]와 s[2k + 1]이 모두 0이라면, 둘 다 flip이 안 되는 것이 좋으므로 ")("를 선택한다.

-> 만약에 s[2k]와 s[2k + 1]이 모두 1이라면, 둘 다 flip되어야 하므로 "()"를 선택한다.

하지만 위의 풀이는 보면 알겠지만, 맨 앞에 ")("가 오는 불상사가 생길 수 있다.

따라서 반드시 "("로 시작하도록 해야하고, s[2k + 1]과 s[2k + 2]를 고려해야 한다. (위의 관찰 2도 수정해야함)