Codeforces Round #750 (Div. 2)

A. Luntik and Concerts

B. Luntik and Subsequences

C. Grandma Capa Knits a Scarf

D. Vupsen, Pupsen and 0

E. Pchelyonok and Segments

F1. Korney Korneevich and XOR (easy version)

A. Luntik and Concerts

번역/요약: \(a\)개의 \(1\)분짜리 노래, \(b\)개의 \(2\)분짜리 노래, \(c\)개의 \(3\)분짜리 노래가 있다. 공연 두 번에 나눠서 모든 노래를 부를 것이다. 두 공연의 공연 시간 차이가 최소가 되게 하고 싶다. 시간 차이의 최솟값을 구하라.

풀이: \(2\mid a+b\) 라면 \(0\), \(2\nmid a+b\)라면 \(1\)이 답이 된다.

증명:

주의:

B. Luntik and Subsequences

번역/요약: 길이 \(n\)의 배열 \(a\)가 주어진다. 배열의 모든 원소의 합을 \(s\)라고 하자. 도훈이는 배열 \(a\)의 부분 수열의 모든 원소의 합이 \(s-1\)이 되면 이 부분 수열을 "거의 꽉 찬 부분 수열"이라고 부른다. 배열이 주어질 때 "거의 꽉 찬 부분 수열"의 개수를 구하라.

풀이: \(0\)과 \(1\)에 주목한다. 왜냐하면 모든 원소는 음이 아닌 정수이고, \(0\)은 합을 변화시키지 않으며 \(1\)만 제외하면 \(s-1\)이 되기 때문이다. 그러면 \(1\) 하나를 선택하고 자유롭게 \(0\)을 선택하므로, \(2^{(0\text{의 개수})}\times (1\text{의 개수})\)가 답이 된다.

C. Grandma Capa Knits a Scarf

번역/요약: 알파벳 소문자로 구성된 문자열 패턴이 주어진다. (\(s,\ |s|=n\)) 도혜 할머니는 회문으로만 스카프를 짤 수 있다. 섬세하지 못한 도훈 할아버지는 제대로 된 회문을 주지 않았다. 근데 도혜 할머니는 기분이 상하지 않도록 알파벳 하나만 선택해 해당 알파벳 자리 일부를 지워내려 한다. 또, 지워지는 기호의 수를 최소화 하려 한다. 가불 여부를 판단하고, 가능하다면 지우는 기호 수의 최솟값을 구하라.

풀이: 모든 문자에 대해 생각하면 된다. \(O(26\times \sum n)\)이다. 정확한 구현이 핵심이다. 필자의 구현이 최고라고는 못하겠지만 그래도 Accepted된 코드다...

F1. Korney Korneevich and XOR (easy version)

번역/요약: 배열 \(a\)(\(|a|=n\))이 주어진다. \(a\)의 모든 증가 부분수열(IS; Increasing Subsequence) \(s\)에 대해, \(s[1]\oplus s[2] \oplus \cdots \oplus s[m]=x\)로 \(x\)를 생성한다. 생성된 모든 \(x\)로 구성된 집합을 생각하고(즉, 중복을 제외시킨다), 그 원소를 모두 출력하라.

풀이: dp를 이용한다. 

증명: 고민중...