Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

lmlmlm

Codeforces Round #794 (Div. 1) 본문

문제풀기

Codeforces Round #794 (Div. 1)

lml 2022. 6. 6. 18:39

https://codeforces.com/contest/1685

 

A. Circular Local MinMax

 

모든 원소들을 모두 정렬한 뒤, 짝수 번째에 올 애들과 홀수 번째에 올 애들을 결정

 

B. Linguistics

 

우선 A와 B의 개수가 맞는지 확인.

이후 AAAA/BBBB/AA/BBB/A/B/A/BBB/... 이런식으로 구간을 쪼갠다.

-> 만일 한 구간의 원소의 개수가 2개 이상이라면 앞쪽 구간과 뒤쪽에서 각각 AB와 BA를 하나씩 만들 수 있다.

-> 만일 한 구간의 원소가 1개라면 제한이 걸린다.

-> 따라서 구간의 원소가 1개인게 반복되는 형태인 ABABAB...BA는 따로 처리해주어야 한다.

-> 만일 A에서 시작해서 A로 끝난다면 만들어질 수 있는 AB와 BA의 개수가 같다.

-> 만일 A에서 시작하여 B로 끝난다면 AB만 모두 박아넣을 경우 일반적인 개수보다 1개 더 만들 수 있다.

-> 따라서 이러한 경우를 미리 저장해두고 마지막에 처리해주면 된다.

 

C. Bring Balance

 

첫 생각 : 최대한 앞뒤에 '('와 ')'를 많이 남겨둔 채로 bracket sequecne를 뒤집는다.

-> 해보면 pref[i] = a[1] + a[2] +... a[i]라 정의할 때 pref값이 제일 큰 부분과 제일 작은 부분을 기준으로 뒤집어주면 된다.

-> 이것보다 더 좋은 방법이 있는지는 알기 어렵다.

 

해답 : pref값이 제일 큰 부분을 기준으로 앞 구간, 뒷 구간을 뒤집으면 balanced가 된다.

-> 따라서 0번, 혹은 1번 뒤집어서 balance하게 만들 수 있는지 확인해주면 된다.

-> 어떤 [L, R]을 뒤집어서 Balance 시키는게 가능한가

-> 그렇다면 [L, R]내부의 모든 i에 대해서 pref[L - 1] + pref[R] - pref[i] >= 0이 되는지만 확인해주면 된다.

-> pref[L - 1] + pref[R]을 최대로 키워버리고 가능한지 찾아주면 된다.

 

D1. Permutation Weight

 

permutation cycle을 봐야함은 어느 정도 명백하다.

-> 처음 생각해냈던 방식은 각 cycle에서 숫자들을 하나씩 따와서 c1, c2, ... ck라고 하였을 때 이들을 정렬하는 것이라 생각

(최대한으로 q[i] = p[q[i + 1]]이 되도록 설정하는 것. 참고로 p가 하나의 큰 cycle이라면 모든 i에서 이것이 성립하도록 가능)

-> 그러면 |ck - c1| + 0 + 0 + |c2 - c1| + 0 + 0 + ... 꼴이 되어 최소가 될 것이라고 생각하였다.

 

하지만 cycle들을 합치는 것이 사실 제일 최선이다.

-> q[i] = p'[q[i + 1]]인 p'이 항상 존재한다. 이때 p'은 반드시 하나의 큰 cycle을 이루고 있어야 한다.

-> 주어진 식은 |p'[q2]] - p[q[2]]| + |p'[q[3]] - p[q[3]]| + ... 이므로 다시 정리하면 S = |p[1] - p'[1]| + |p[2] - p'[2]| + ...이다.

.초기에 p' = p라고 설정하자. 이제 p'이 하나의 cycle이라는 것을 만족시키기 위해서 p'에 작업을 가하자

-> 만일 i와 i + 1이 서로 다른 cycle에 존재한다면 이 둘을 서로 swap하여 S를 2 증가시키고 둘이 같은 cycle에 있도록 하자.

-> cycle들은 총 k - 1번 합해지므로 최댓값은 2 * (k - 1)

이것은 아마도 최솟값이다!

 

D2에 상당히 긴 증명과 permutation을 구하는게 서술되어 있는데 추후에 찾아볼 것.

댓글에 IOI2016 - Roller Coaster Railroad와 연관이 있다는 이야기도 있음.

Comments