Codeforces Deltix Round, Summer 2021

총평

무난한 퀄리티의 Div1 + Div2 대회. 근데 내 코드 왜 맞지 ㅋㅋ;

대회 후기

7647점. Official 기준 64등에 해당한다. 레이팅 +30 정도의 퍼포먼스. (대회 63등 한 사람이 원래 지금 내 레이팅이랑 똑같았는데 30점 올랐다)

A는 쉬워서 바로 짜서 내고, B는 약간 시간이 걸렸지만 역시 전형적인 문제라서 금방 풀었다.

C를 봤는데 대충의 풀이는 빨리 나왔지만 Off-by-one을 신경쓰는 것이 상당히 거슬리는 문제였다. 이런 거 잘 못하는데.. 다행히도 예제가 3개나 있길래 여기저기 1을 더하고 빼고 해 보다가 예제 3개가 다 맞는 조합을 찾아서 냈더니 맞았다. 이 무슨..

D에 인터랙티브가 있길래 뭔가 했는데, 걍 노잼문제였다. (a & b) + (a | b) = a + b 임을 떠올리면 바로 풀리는 문제.

E를 처음 보고 어려워 보이길래 + tourist가 F를 풀었길래 F를 잠깐 봤는데, 잘못된 판단이었다. tourist는 사람이 아닌 게 분명하다. 아무튼 E를 한 10분 동안 보다가, 증명은 잘 못 하겠지만 뭔가 맞을 것 같은 풀이를 짜서 예제를 넣어 봤더니 틀렸다. 다행히도 좀 더 맞을 것 같은 풀이를 곧 떠올려서 금방 고쳐서 냈더니 맞았다. 이건 진짜 왜 맞는지 모르는 채로 맞았다 ㅋㅋㅋ

F를 이젠 풀어야겠다 싶어서 열심히 생각을 해 본 결과, "나한테서 도달 가능한 애들의 집합"을 고정하는 아이디어를 떠올렸다. 처음에는 거기서 포함배제를 돌릴 수 있다는 이상한 생각을 해서 이상한 코드를 짰더니 예제도 안 나왔는데, 시간을 조금 더 쓰고 나니 그 아이디어를 DP로 구현하면 포배 쓸 필요 없이 단순 확률 곱셈 덧셈이 된다는 것을 깨달을 수 있었다. 근데 처음에 개느린 코드를 짜서 TLE 하나 먹고, 최적화하느라 한 20분 썼다 ㅋㅋ;; 이거 빨리 못 푼 게 상당히 아쉽다.

G랑 H를 봤는데 시간 안에 못 풀겠다 싶어서 걍 접었다.

끝나고 보니까 G를 좀 더 잡아 봤으면 어땠을까 하는 생각도 든다.

문제별 풀이

A

a+b의 값이 홀수면 절대 만들 수 없음을 일단 알 수 있다.

a+b의 값이 짝수이면, a=b일 경우 둘 다 a씩 더하면 1번만에 되고, 그렇지 않으면 2번만에 된다. a=b=0일 경우 답이 0임에 유의. (다행히도 예제에 있다)

코드 : http://codeforces.com/contest/1556/submission/127507298

B

결국 각 수의 홀짝성만 중요하므로 배열의 원소를 0 또는 1로 바꿔서 생각하자.

인접한 두 수의 홀짝성이 달라야 하므로 배열의 모습은 "0 1 0 1 ..." 또는 "1 0 1 0 ..." 의 꼴이어야만 한다. 두 가지 케이스 각각에 대해 0과 1이 각각 몇 개씩 필요한지 정확히 결정되므로, 0과 1의 개수가 거기에 맞지 않으면 불가능이다.

개수가 딱 맞는다면, 0을 처음 배치에서 원하는 배치로 옮기기 위한 (1을 옮긴다고 생각해도 동일함) 최소 횟수를 구하면 된다. 앞에 있는 0과 뒤에 있는 0의 순서를 바꿀 이유가 전혀 없으므로 원래 0의 위치가 (앞에서부터) a[1], a[2], ..., a[k]이고 최종 상태의 0의 위치가 b[1], b[2], ..., b[k]라고 하면 |a[i]-b[i]|를 모두 더한 값이 답이 된다.

코드 : http://codeforces.com/contest/1556/submission/127507696

C

올바른 괄호 문자열의 시작은 무조건 '(', 끝은 무조건 ')' 이므로 "(((...((( 의 어딘가"에서 시작하여 ")))...))) 의 어딘가"에서 끝나는 부분 문자열만이 올바른 괄호 부분문자열이 될 수 있다.

"높이"를 처음에 0으로 두고, 괄호 문자열을 왼쪽부터 보면서 '('를 만날 때마다 높이가 1씩 올라가고 ')'를 만날 때마다 1씩 내려가는 수열을 만들 수 있다. 예를 들어, "(()(())"에 해당하는 수열은 "0 1 2 1 2 3 2 1" 이다. 참고로 이 수열은 괄호 문자열 문제에서 매우 자주 쓰이는 수열이다.

이제, (((( 부분과 )))) 부분을 하나씩 잡으면 그 사이에서 만들어지는 올바른 괄호 문자열은 다음 조건을 만족해야 한다.

- 시작 부분과 끝 부분의 높이가 동일하다.
- (시작~끝 사이에서 만나는 가장 낮은 높이)가 (시작 부분 높이) 이상이어야 한다.

왼쪽 (((( 부분을 고정하고, )))) 부분을 오른쪽으로 보내면서 (시작~끝 사이에서 만나는 가장 낮은 높이)를 계속 갱신해 나가면 각 쌍에 대한 답을 O(1)에 구할 수 있다.

+ 이렇게 말로만 하면 쉬운데, 식의 어떤 부분에서 1을 더해줘야 하는지, 빼줘야 하는지가 상당히 헷갈린다... 나는 이것저것 바꿔보다가 예제 3개가 다 맞는 조합을 찾아서 냈다.

코드 : http://codeforces.com/contest/1556/submission/127508444

D

임의의 a, b에 대해, a + b = (a & b) + (a | b) 가 성립한다. 예제를 하나 보면 이해가 쉬울 것이다.

a  110110    a&b  010100
b  011101    a|b  111111
  1010011        1010011

이제, 임의의 두 수 a[i], a[j]에 대해 2번의 쿼리(or i j, and i j)로 a[i] + a[j]의 값을 알 수 있다.

n >= 3이므로, a[1] + a[2], a[2] + a[3], a[3] + a[1]의 값을 각각 알아내면 a[1], a[2], a[3]의 값을 6번의 쿼리로 계산할 수 있다. 이제, k >= 4에 대해 a[1] + a[k]의 값을 2번의 쿼리로 알아내면 a[k]의 값 역시 바로 알 수 있으므로 총 6 + 2(n-3) = 2n번의 쿼리로 모든 a[i]의 값을 알 수 있다.

개인적으로 C번보다 좀 더 쉽다고 생각.

코드 : http://codeforces.com/contest/1556/submission/127508883

E

c[i] = b[i] - a[i] 라고 정의하면, 각 쿼리의 목표는 어떤 구간 내의 c[i] 값을 모두 0으로 만드는 것이 된다. 그리고 각 연산은 구간 내의 짝수 개 원소를 골라서 왼쪽부터 순서대로 "-1, +1, -1, ..."을 적용하는 것이 된다.

일단 모두 0으로 만드는 것이 가능한지 여부부터 생각을 해 보자. 여기서는 C에서도 써먹었던 "올바른 괄호 문자열"을 도입할 수 있다. c[i] > 0이면 해당 자리에 '('를 c[i]개 놓고, c[i] < 0이면 ')'를 -c[i]개 놓은 괄호 문자열을 생각하자. 각각의 연산은 '(', ')', '(', ')', ... 의 괄호 쌍들을 앞에서부터 골라서 지우는 것이고, "모두 0으로 만들기"는 "문자열의 괄호 문자들을 모두 지우기"와 동일하다. 즉, "가능한지 여부" = "구간에 해당하는 괄호 문자열이 올바른 괄호 문자열임" 이 성립한다! 올바른 괄호 문자열인지의 여부는 아래 2가지 조건으로 판별할 수 있다.
- 구간의 c[i] 값 합이 0
- 구간에서 c[i]의 prefix sum들 중 최솟값이 0 이상

이제 최소로 필요한 연산 횟수를 생각해 보자. 각 연산은 각각의 (c[i]의 prefix sum) 값을 많아야 1 감소시킨다. 따라서, 적어도 "c[i]의 prefix sum 중 최댓값"만큼의 연산이 필요하다. 이제, 각각의 연산에서 "가장 안쪽에서 매칭된 괄호 쌍"들을 모두 지운다고 생각하자. 예를 들어 "(())(()())" 과 같은 괄호 문자열이 있다면 빨갛게 색칠된 2, 3, 5, 6, 7, 8번째 문자를 지우는 것이다. 이를 반복하면 정확히 "c[i]의 prefix sum 중 최댓값"만큼의 연산 횟수로 모든 문자를 지울 수 있음을 알 수 있다.

임의의 구간에서 위에 설명한 값들을 빠르게 구하는 것은 분할 정복으로 이 문제를 푸는 과정을 세그먼트 트리로 모델링함으로써 구현할 수 있다. 구간마다 전체 합, prefix sum 최솟값/최댓값의 3가지 값을 관리하면 된다. 무슨 말인지 잘 모르겠다면 구글에 "금광 세그"를 검색하자.

+ 사실 대회 중에는 위에 열심히 쓴 내용 중 대부분을 증명 없이 대충 짐작만 한 채로 냈다. ㄹㅇ 왜 맞았지;;

코드 : http://codeforces.com/contest/1556/submission/127510465

F

기댓값은 선형성을 가지므로, 각 선수에 대해 "그 선수가 winner가 될 확률"을 구해서 다 더하면 답이 됨을 알 수 있다.

예제 설명 그림에 있는 그래프처럼 임의의 i, j (i≠j) 쌍 사이에 i -> j 또는 j -> i 간선 중 정확히 하나만 존재하는 그래프를 "Tournament Graph"라고 하는데, 이 때 어떤 정점 x가 "winner"라는 것은 x에서 다른 모든 정점으로 도달이 가능하다는 것이다.

선수 x를 고정하고, 그 선수에서 도달 가능한 선수들의 집합 S를 고정해 보자. 만약 그 집합이 전체집합이라면, 그 선수는 winner가 된 것이다. 그렇지 않다면, 그 선수는 winner가 아닌 것이고, 그런 상황이 일어날 확률은 (S에 속하지 않은 모든 선수가 S에 속한 모든 선수를 이겼을 확률) * (x가 S 내에서 winner일 확률)이다.

이제 bitmask DP를 설계할 수 있다. dp[x][S] : "(x를 포함하는) S 내에서 x가 winner일 확률" 이라고 정의하면, dp[x][S]의 값은 1 - (x를 포함하는 모든 S의 진부분집합 T에 대해, (S-T에 속한 모든 선수가 T에 속한 모든 선수를 이겼을 확률) * dp[x][T]의 합) 으로 계산할 수 있다. 문제의 답은 dp[x][전체집합]들의 합이 된다.

각 S에 대해 S의 진부분집합을 다 돌아야 하므로 시간복잡도에 일단 O(3^N)이 들어간다. 코딩을 무지성으로 해서 O(N^3 3^N) 같은 걸 짜면 TLE가 날 수 있으니 적절한 최적화가 필요하다.

코드 : http://codeforces.com/contest/1556/submission/127514439

G

대회 중에는 못 풀었다. Editorial 읽고 업솔빙 예정.

H

매트로이드를 알아야 풀 수 있는 거 같다. 공부를 해야 하나..