[Codeforces] Educational Codeforces Round 120 후기

퍼플따리라서 에듀가 rated contest이다.

후...

C에서 좀 말려서 E를 그렇게 늦게 풀지 않았음에도 랭킹이 상당히 낮았다. 앳코더를 열심히 해서 그런지 코너 케이스나 기타처리가 좀 미숙해졌다는 걸 느꼈다. 구현실력도 줄어들고. 코포도 레드 찍기로 마음 먹었으니 힘을 더 내야겠다.

 

오늘 풀지 못한 F는 정수론 문제로 보였는데, 내가 정수론을 잘 몰라 정수론 문제가 나올 때마다 숨이 턱턱 막힌다. 날잡고 정수론 웰노운이나 유용한 알고리즘들을 배워야겠다. 특히 디리클레 합성곱인가 그거.. 그거 꼭 배워야지

 

https://codeforces.com/contest/1622

 

A

막대 3개가 있는데 하나를 부러뜨려서 직사각형을 만들 수 있는지 판별하는 문제다.

 

일반성을 잃지 않고 $a \leq b \leq c$라고 할 때 $a+b=c, a=b \textrm{ and } c = 2k, b=c \textrm{ and } a=2k$ 세 경우밖에 없다.

 

B

순열 $p$가 주어지고 $0, 1$로만 이루어진 문자열 $s$가 주어진다. $s_i=1, s_j=0$이면 $q_i>q_j$가 되도록 새로운 순열 $q$를 만들 때, $ \sum |p_i-q_i|$의 최소는?

 

$s_i=1$인 집합과 $s_i=0$인 집합으로 나누어 $1$인 집합에는 $n, n-1, \cdots$를 할당하고, $0$인 집합에는 $1, 2, 3, \cdots$를 할당하면 된다. 이제 각 집합에서도 각 원소의 인덱스에 어떤 숫자를 할당할지가 문제인데, 자명하게 그리디로 $p_i$가 커지는 순대로 정렬한 뒤 할당할 숫자를 순서대로 배치하면 된다. 

 

C

후... 여기서 시간을 너무 버려서 5솔인데 등수가 낮다

배열이 주어질 때, 한 숫자를 다른 숫자로 바꾸거나 한 숫자를 $1$ 줄일 수 있을 때, 배열 전체 합이 $k$ 이하가 되도록 하는 최소 횟수를 구하는 문제이다.

 

자명하게, $1$ 줄이는 연산은 가장 작은 원소에만 하면 된다. 이후 다른 숫자로 바꿀 숫자는 항상 큰 수부터 뽑는 것이 이득이다. 또 당연하게도 가장 작은 원소를 어느 수준까지 줄인 후 다른 숫자로 바꾸는 연산들을 진행하는 것이 최적이다. 따라서 다른 숫자로 바꾸는 연산을 할 원소 개수를 정하면 총 몇 번의 연산이 필요한지 계산할 수 있다.

 

우선 다른 숫자로 바꿀 숫자를 0개 뽑는 처리를 하지 않았었고, 처음 구현에서는 음수 나눗셈이 문제였는지 자꾸 틀렸다. 결국 D를 푼 뒤 AC를 받긴 했으나 D, E를 빨리 풀었음을 감안하면 이 문제를 빨리 풀었다면 50등권도 가능하지 않았을까 생각한다.

 

D

$0$과 $1$로만 이루어진 문자열 $s$가 주어진다, $k$개의 1을 포함한 부분 문자열을 한 번 섞을 수 있을 때, 변환 가능한 문자열의 개수는?

 

$i$번째 $1$의 위치를 $p_i$라고 할 때, $p_{i+1}, \cdots, p_{i+k}$를 원래와 다르게 섞을 수 있는 경우의 수는 총 $_{p_{i+k+1}-p_i}C_{k}-1$임이 자명하다. 다만 이 경우와 $p_{i}, \cdots, p_{i+k-1}$이나 $p_{i+2}, \cdots, p_{i+k+1}$을 섞는 경우가 겹칠 수 있는데. 전자의 경우만 생각을 해보면 $i$번째와 $i+k$번째 $1$이 원래 위치일 때 항상 겹친다는 것을 알 수 있다. 비슷한 논리로 겹치는 경우의 수는 $_{p_{i+k}-p_i}C_{k-1}-1$이다. 모든 연속한 $k$개의 $1$에 대해 경우의 수를 더하고 겹치는 경우의 수를 뺀 후 원래 문자열 경우를 고려해 $1$을 더해주면 답을 얻을 수 있다.

 

E

학생이 $n\leq10$명이 있고 문제가 $m$개 있다. 각 문제의 배점은 순열 $p$로 정할 수 있고, 각 학생이 어떤 문제를 맞추고 틀릴지 미리 주어진다.(문자열로) $i$번째 학생의 기대총점이 $x_i$, 실제 득점이 $r_i$ 때, $ \sum |r_i-x_i|$을 최대화하는 방법은?

 

$n$이 $10$인 것부터 비트 냄새가 솔솔 난다. 각 학생에 $r_i-x_i$ 또는 $x_i-r_i$를 더하게 되는데, 이를 미리 정해주자. 그러면 반드시 실제 대소관계가 식을 만족시키지 않는 경우 어차피 최적해보단 작게 되기 때문에 답이 아니게 된다. 이제 $r_i$와 $x_i$의 부호를 결정했으면 $x_i$는 정한대로 더하고 빼주면 된다. 이제 $r_i$의 합을 결정할건데, $j$번째 문제를 $i$번째 학생이 맞았다고 한다면 $r_i$가 양수일 때는 $p_j$를 더하게 되고 음수인 경우 빼게 되므로, $p_j$를 총 몇 번 더하거나 빼는지 구할 수 있게 된다. 많이 더할수록 큰 수를 배치하는게 항상 이득이므로, 정렬한뒤 그리디하게 배치하면 된다. 이러한 방법들 중 저 특성값을 최대화하는 경우에 대해 답을 출력하면 된다.

 

F는 어려웠다. 풀이방송을 잠깐 봤는데 n이 홀수일 때 n-1 또는 n-3이 답이라고 한 걸 본 것 같다. 왜인지는 잘 모르겠다.