Codeforces Round #792 (Div. 1 + Div. 2)

A에 의해서 본 손해가 이만저만이 아니라 거두절미하고 시작.

 

A. Digit Minimization

 

k = 2일 때에 첫 번째 숫자는 답으로 제출할 수 없다.

 

B. Z mod X = C

 

주어진 숫자에 대해서, a + b + c, b + c, c를 제출하면 된다.

이 문제 또한 문제의 조건을 잘못 읽어 (x, y, z < 1e8) 상당히 고생했다.

왜 굳이 a, b, c < 1e8이라고 했는지는 아직도 의문이다.

 

C. Column Swapping

 

우선 주어지는 table 자체가 good한지 확인한다.

-> good에서부터 벗어나는 열들을 set이든 뭐든 아무튼 저장해 둔다.

이때 good에서 벗어나는 열들의 개수가 3개 이상이라면 무조건 불가능하다.

벗어나는 열 두 개를 바꿨을 때에 이제 good한지만 확인해주면 된다.

https://codeforces.com/contest/1684/submission/157697003

 

D. Traps

 

무조건 K개의 점프를 모두 사용하는 것이 이득이다.

그렇다면 어떤 지점 i에서 점프를 사용하면, 그로 인한 이득이 a[i] - (n - i - 1)이라고 생각해도 무방하다.

물론 i < j 인  j에서 또 점프를 쓴다면 (n - i - 1)만큼 비용이 증가하는 것이 아니라 (n - i - 2)만큼 증가하며

k < i인 k에서 이미 점프를 썼다면 a[i] + 1만큼의 비용이 0이 되는 것이다.

하지만 어차피 K번의 점프를 할 것이니 점프간의 상호작용에 의한 비용변화는 k*(k - 1)/2로 일정하다.

따라서 제일 많은 비용을 절감할 수 있는 k개를 선택해주면 된다.

https://codeforces.com/contest/1684/submission/157701448

 

E. MEX vs DIFF

 

만들 수만 있다면 MEX값을 최대인 상황이 무조건 이득인 상태이다.

-> 이미 중복되는 애를 이용하여 MEX를 증가시켰을 경우 DIFF가 1 증가하고 MEX가 1 이상 증가하여 이득

-> 중복되지 않는 애를 이용하여 MEX를 증가시켰을 경우 DIFF는 유지되고 MEX는 1 이상 증가하여 이득

-> 따라서 MEX를 증가시키는 행위는 무조건 이득이고 MEX를 많이 늘려놓는 것이 좋다.

MEX를 증가시킬 때 위를 보면 알겠지만 중복되지 않는 애를 이용하는 것이 이득이다.

-> 따라서 MEX보다 큰 숫자들 중에서 개수가 적은 애들부터 이용하여 MEX를 증가시켜주면 된다.

https://codeforces.com/contest/1684/submission/157695549

 

하지만, 대부분의 사람들이 위의 풀이를 생각했겠지만, 다들 한 번씩 틀려서인지 다른 풀이들을 하나씩 내놨다.

사실 에디토리얼도 모든 MEX값들에 대한 DIFF값을 구해서 최솟값을 구했다.

이건 각자의 방법으로 잘 구하면 된다. (BIT든, segtree든, set을 잘 활용하든...)

 

F. Diverse segments

 

우선 [0, R]에 작업을 해주면 문제가 원하는 조건을 만족하게 되는 R을 우선 구해주자.

-> 모든 숫자 x에 대해서 [x', x]면 겹치는 원소가 하나도 없도록 하는 최대의 x'들을 모두 구해준다.

-> 그러면 문제에서 주어지는 [l, r]에 대해서 r' >= l인 모든 r'의 최댓값이 R이 된다.

 

이제 L = 0이었던 상태에서 L을 하나씩 증가시키면 된다.

새로운 구간들이 [L + 1, R]이라고 하자. 

a[L]이 이제 변환시키는 구간에서 벗어난다면 

i) [R + 1, r] 중에서 a[L]과 겹치는 애가 없다. ii) [l, L) 중에서 a[L]과 겹치는 애가 없다.

-> 이 두 조건만 확인해주면서 L과 R을 적당히 증가시켜주며 길이의 최솟값을 구하면 된다.

https://codeforces.com/contest/1684/submission/157996083

 

G. Euclid Guess

 

이 문제는 정말 10분만 일찍 봤어도 풀 수 있었을 것이다.

X를 그대로 뱉어낼 수 있는 방법 : 2*X, 3*X를 이용한다.

X를 X의 약수인 d를 활용하여 뱉어낼 수 있는 방법 : 2*X + d, X + d를 이용한다.

-> 따라서 3*X <= m인 애들을 left에, 나머지는 right에 박아두고 이분매칭을 해주면 된다.

https://codeforces.com/contest/1684/submission/157973556

 

H. Hard Cut

 

비트가 한 개라도 있는 string이 주어진다면 무조건 가능하다.