Codeforces Round #742

총평

매우 전형적인 div2 라운드라고 할 수 있다.

대회 후기

8378점. 복붙충 제외 4등. 오늘은 좀 괜찮게 친 거 같다.

A를 0분 59초째에 내서 페널티 안 먹기에 성공했다. B는 A만큼 빨리 풀지는 못 했지만 그래도 적당히 잘 풀었다.

C를 딱 열었는데 모르겠어서 일단 D로 넘어갔다. 다행히도 D는 바로 알겠어서 짰다. 그 다음에 E를 봤는데 E도 바로 알겠어서 짰다 (??) 다행히도 이번에 C를 봤을 때는 풀이가 떠올라서 짰다.

F가 남았는데, 대충의 관찰은 금방 되었으나 뭔가 한 부분에서 막혔다. (주변 4칸이 다 .인 X를 어떻게 처리할지) 그러다가 이상한 가정을 하나 한 풀이를 냈는데 틀리길래 "아 이거 아닌가..." 했다. 그런데 한 5분쯤 후에 내가 그 코드를 잘못 짰다는 걸 깨닫고 고쳐서 냈더니 맞았다. 왜 맞지 ㅋㅋ;

요즘 버추얼을 치면 꼭 한 문제씩은 왜 맞는지 모르는 채로 맞는 것 같다. 좋은 건지는 잘 모르겠다.

문제별 풀이

A

주어진 문자열에서 'U'는 'D'로, 'D'는 'U'로 바꾸면 된다.

코드 : http://codeforces.com/contest/1567/submission/128109353

B

일단 MEX를 a로 만들기 위해서는 0, 1, ..., a-1이 적어도 하나씩은 있어야 하니, 걔네들을 일단 넣어 놓고 생각하자.

이제 XOR 값을 b로 만들어 줘야 하는데, X = 0 ^ 1 ^ 2 ^ ... ^ (a-1) 이라고 할 때 X의 값에 따라 세 가지 케이스가 있다.

i) X = b
0부터 a-1까지 하나씩 넣은 시점에서 이미 두 조건을 모두 만족했으니, 답은 a가 된다.

ii) X ^ b ≠ a
X^b를 하나 더 넣어 주면 XOR 값이 b가 되고, MEX 값은 여전히 a이다. 답은 a+1.

iii) X ^ b = a
X^b=a를 넣어서 XOR값을 b로 만든 건 좋은데, 이 경우에는 MEX가 변해 버려서 그러면 안 된다. 따라서 적어도 2개를 더 추가해야 하는데, 둘이 XOR해서 X^b가 나오는 a와 다른 두 정수를 어떻게 잘 찾을 수 있다고 믿고(?) a+2를 답으로 해서 내면 맞는다.
(+ 굳이 증명을 하자면... X^b=a가 1이면 2랑 3을 / 1 초과의 홀수면 1이랑 a-1을 / 짝수면 1이랑 a+1을 넣어 주면 된다.)

코드 :  http://codeforces.com/contest/1567/submission/128109646

C

예제를 가지고 열심히 관찰하다 보면, Alice가 덧셈을 수행하는 방식이 아래와 같음을 알 수 있다.

- 주어진 수들을 홀수번째/짝수번째 자리로 각각 쪼갠다.
- 각각에서 제대로 된 덧셈을 수행한다.
- 그 결과를 다시 홀수/짝수 자리 교대로 적는다.

예제에 나온 "2039 + 2976 = 15005" 가 나오는 과정을 생각해 보면, 홀수번째 자리 (09 + 96 = 105) 와 짝수번째 자리 (23 + 27 = 50) 의 올바른 덧셈 결과를 교대로 적어서 15005가 나온 것을 볼 수 있다.

이제, Alice식 덧셈의 결과가 n이 나오게 하기 위해서는 n의 홀수번째 자리 / 짝수번째 자리를 각각 쪼개서 만든 수 (a, b라고 하자) 에 대해 그냥 (x+y=a인 음 아닌 정수 (x,y) 쌍의 수) * (z+w=b인 음 아닌 정수 (z,w) 쌍의 수) 를 하면 답이 된다! x+y=a인 음 아닌 정수 (x,y) 쌍의 수는 a+1임을 쉽게 알 수 있다.

이제 이걸 짜서 예제를 넣어 보면 모든 케이스에서 답이 2만큼 차이날 것이다. 실제로는 위에 말한 값에서 2를 뺀 값이 답이 되는데, (x와 z) 또는 (y와 w)가 모두 0이 될 경우 "positive integer" 조건에 위배되기 때문이다.

코드 : http://codeforces.com/contest/1567/submission/128111516

D

우선 관찰할 점은 "최대한 높은 자릿수를 많이 남기는 것이 이득이다" 라는 것이다. 즉, 110을 11 10개로 쪼개는 것보다 101과 1 9개로 쪼개는 편이 낫다는 뜻이다.

결국 수를 적어도 자연수 n개로 쪼개야 하므로, 원래 숫자의 자릿수 합이 n 이상이라면 최대의 이득을 볼 수 있다. 이 때 각 수에 배분을 어떻게 하든지 상관이 없음은 쉽게 알 수 있다. 예를 들어, "112"를 수 3개로 쪼개야 한다면 101+10+1, 110+1+1, 100+11+1 등등이 모두 같은 결과(134)을 낸다.

한편, 원래 숫자의 자릿수 합이 너무 적으면 \( 10^k \) 자리에 있는 1을 \( 10^{k-1} \) 자리에 있는 1 10개로 쪼개는 것을 여러 번 반복해서 자릿수 합이 n 이상이 되도록 해 주어야 한다. 이 때 당연히 최대한 낮은 자리에 있는 것부터 쪼개주는 것이 좋다. n이 그렇게 크지 않기 때문에 대충 구현해도 시간 안에 충분히 나온다.

코드 : http://codeforces.com/contest/1567/submission/128110065

E

"금광 세그트리"에 대해 알고 있다면, 매우 유사한 방식으로 이 문제를 해결할 수 있을 것이다. 혹시 이 말을 처음 듣는다면, 구글에 "금광 세그트리"를 검색하고 오자. 진짜 여기저기 엄청 많이 나오는 테크닉이다.

아무튼, 결국 중요한 것은 이 문제를 "분할 정복"으로 어떻게 풀 것이냐이다. 문제에서 구하는 값은 수열에 존재하는 각각의 non-decreasing 덩어리들에 대해 (예를 들어, [3, 1, 2, 4, 3, 2, 2, 3]의 경우 3 / 1,2,4 / 3 / 2,2,3 으로 나누어짐) \( l(l+1)/2 \) (단, \( l \)은 각 덩어리 길이) 를 모두 합한 값이다.

수열을 반으로 쪼개서 각각 다음의 값을 구했다고 하자.
- 이 구간 내에서 non-decreasing subarray의 개수
- 맨 왼쪽 / 맨 오른쪽 덩어리 길이

위 값들을 알면 두 수열을 합친 것에 대해서도 위에 말한 값들을 구할 수 있다. 두 수열이 합쳐진 부분, 즉 정가운데를 지나는 덩어리가 어떻게 되는지를 살펴보면 된다. 디테일은 코드를 참고하자.

코드 : http://codeforces.com/contest/1567/submission/128110812

F

어떤 X 주변에 빈 칸이 홀수 개 있으면 절대로 조건을 만족시킬 수 없다. 우선 이것을 모두 체크하자.

이제, 각 X 주변에는 0개, 2개 또는 4개의 빈 칸이 있다. 0개일 경우는 별로 신경쓸 게 없으니 스킵하고, 2개 / 4개인 경우에 주목하자.

빈칸이 2개일 경우, 둘 중 하나는 1이고 하나는 4여야 한다. 빈 칸을 1 또는 4로 coloring한다고 생각하면, 해당하는 2개의 빈칸 사이에 간선을 이은 그래프에서 2색 coloring을 진행한다고 생각할 수 있다. 그렇게 간선을 이었을 때 이분그래프가 되는지는 잘 모르겠으나 일단 된다 치고(??) 진행해 보자.

빈칸이 4개일 경우에는 자유도가 좀 더 높은데, 1 2개와 4 2개를 어떻게든 배치하면 되기 때문이다. 그런데, 이렇게 하면 위에서 말한 이분그래프 모델링을 사용하기 어렵기 때문에, 그냥 마음대로 제한을 더 걸어서 X 주변에 마름모 모양으로 간선 4개를 이어 버리자. 즉, 다음 2가지 배치만 가능하도록 제한하는 것이다.

_ 1 _          _ 4 _
4 X 4   or   1 X 1
_ 1 _          _ 4 _

이렇게까지 하면 더더욱 이분그래프가 될 이유가 없어 보이지만, 이대로 구현을 해서 내면 맞는다.
??
Editorial 풀이는 내 풀이랑 좀 다른 거 같아서 잘 모르겠다.

(무책임한 풀이 죄송합니다..)

코드 : http://codeforces.com/contest/1567/submission/128113836