[CF] Codeforces Round #821 (Div. 2)

https://codeforces.com/contest/1733

Dashboard - Codeforces Round #821 (Div. 2) - Codeforces

C. Parity Shuffle Sorting (Upsolved)

무조건 n-1번의 연산으로 비내림차순 수열을 만들 수 있다. 정확히는 모든 수가 같은 수열을 만들 수 있다. 첫 연산에서 맨 앞과 맨 뒤를 연산하고, 나머지 n-2번의 연산에서는 가운데 n-2개의 수들을 맨 앞 또는 맨 뒤와 더해서 모두 같게 만들면 된다.

D1. Zero-One (Easy Version) (Upsolved)

x>=y라는 조건을 까먹고 있었어서 못 푼 점도 있는 거 같아서 아쉽다. 문제를 잘 읽어야겠다. a, b를 문자열로 입력받고, 서로 다른 것의 개수를 세어줘야 하니까 XOR 연산을 이용하면 편하다. 서로 다른 것의 개수를 cnt라 할 때, cnt의 개수가 홀수면 절대 두 문자열을 같게 만들어 줄 수 없다. 따라서 cnt의 개수가 짝수인 경우만 살펴보면 되는데, 여기서 작은 경우부터 생각해주는 것이 간단하다.
'cnt == 2 && 그 두 개가 붙어있음' 일 때에는 답이 n>=5 이므로 min(x, 2*y)이다.
'cnt == 2 && 그 두 개가 떨어짐'일 때에는 답이 y이다.
'cnt > 2'인 경우는 모든 서로 다른 것끼리 떨어져 있도록 선택해 줄 수 있으므로, y*cnt/2가 답이다.