알고리즘/온라인 대회

Codeforces Round #737

kdh9949 2021. 8. 23. 20:18

Div2 Only 대회였다. 간만에 Div2 대회 Virtual이 치고 싶어서 쳤다.

총평 : 노잼문제 4개 + 이상한문제 1개.

Virtual 참가 후기

더보기

어차피 Unofficial 참가자가 훨씬 많으니까 그냥 포함해서 얘기하면 (위에 복붙충 2명 제외) 9등이다. B에서 시간 끈 거 치고는 E를 빨리 풀어서 나쁘지 않은 듯?

A를 열었는데 Div2A 답지 않게 좀 어려워 보였다. "혹시 이건가?" 싶었던 생각을 구현해 보니 예제가 다 나오길래, 그냥 냈더니 맞았다. 요즘 Div2 빡세다..

B를 열었는데 랑 똑같이 생겼길래 "오 개꿀" 하고 그 문제 정답 코드랑 똑같은 알고리즘을 짜서 냈는데 틀렸다. 왜 틀렸는지 5분 동안 고민하다가 문제를 다시 읽었는데 백준 걔는 연산 횟수에 제한이 없고, 여기는 "단 1회"라고 볼드체로 써 있었다. 눈물을 흘리면서 다시 짜서 냈다. 그 와중에 2번 더 틀림 ㅋㅋ

C는 전형적인 코포-스타일 비트 AND XOR 어쩌구 문제였고, 홀/짝 케이스 나눠서 각각 경우의 수 세면 풀리는 노잼문제였다. 노잼.

D는 역시 노잼 자료구조 DP 문제였다. 근데 Div2D에 lazy 세그가 나오는 게 맞나 싶긴 하다. lazy 세그 안 쓰면 못 풀게 생겼던데.. editorial을 봐야겠다.

E는 체스 판에서 퀸을 잘 움직여서 은신한 킹을 잡는 문제였는데, 뭔가 묘하게 어려웠다. 일단 대충 생각나는 방법을 슥슥 짜서 내 봤는데, 맞아서 어이가 없었다. (로컬에서 테스트하기도 힘들길래 걍 냈었다) 왜 맞지?

하여튼 78분만에 다 풀어서 블로그 글도 바로 쓰고 좋았다. B에서 똥 안 쌌으면 좀 더 좋았을 것 같은데.. 그게 좀 아쉽다. 아무튼 이렇게 쉬어가는 느낌으로 대회를 치니까 좋은 것 같다.

 

A

배열을 두 개의 집합 A, B로 나눠서 (A의 평균) + (B의 평균)을 최대화해야 한다. 집합으로 나누었을 때 원래 배열의 각 수에 붙는 계수는 1/(집합 크기) 인데, 모든 계수를 다 합하면 항상 2가 된다. 이제 가장 큰 값에 계수를 다 몰아주는 것이 최적이므로, 제일 큰 수만 집합 하나에 따로 떼 놓고 나머지를 다 반대쪽에 넣으면 된다.

풀이가 아무리 봐도 Div1A는 아닌데.. 잘 모르겠다. 예제 보고 때려맞히라고 낸 건가?

코드 : http://codeforces.com/contest/1557/submission/126745495

 

B

배열이 주어지고, 이 배열을 k개의 조각으로 나눈 다음 조각을 재배열해서 정렬할 수 있는지 판단해야 한다. 연산을 단 한 번 할 수 있으므로, 원래 배열에서 인접한 두 수가 정렬한 뒤에는 인접하지 않다면 그 사이를 무조건 잘라주어야 한다. 또한, 그런 곳을 모두 자르고 나면 정렬이 무조건 됨을 쉽게 알 수 있다. 그렇게 잘랐을 때 조각이 k조각 이하인지에 따라 Yes나 No를 출력해 주면 된다.

원래 배열에서 인접한 두 수가 정렬한 뒤 인접함을 확인하는 가장 쉬운 방법은 좌표 압축을 한 뒤 a[i+1] - a[i] = 1인지 확인하는 것이다. 요즘 Div2B는 좌표 압축도 할 줄 알아야 풀 수 있나 보다.. 이거 맞나?

코드 : http://codeforces.com/contest/1557/submission/126746330

 

C

k비트짜리 이진수로 이루어진 길이 n의 수열들 중 (모든 값 AND) >= (모든 값 XOR) 인 수열의 개수를 구하는 문제이다. 비트 별로 쪼개서 생각해 보자. n의 홀짝성에 따라 케이스를 나눌 수 있다.

n이 홀수 : 어떤 비트의 전체 AND값이 1이면 XOR값 역시 1이다. AND값이 0일 경우, XOR값은 1이 홀수개면 1, 짝수개면 0이다. 어떤 경우에도 AND값 <= XOR값이므로, 모든 비트에 대해 AND값 = XOR값인 수열의 개수를 구하면 된다. 각 비트마다 AND값과 XOR값이 둘다 1이거나 둘다 0이면 되는데, 둘다 1인 경우는 1가지(싹 다 1)이고 둘 다 0인 경우는 \( \binom{n}{0} + \binom{n}{2} + \cdots + \binom{n}{n-1} = 2^{n-1} \) 이다. 답은 \( (2^{n-1} + 1)^k \) 이다.

n이 짝수 : 어떤 비트의 전체 AND값이 1이면 XOR값은 0이다. AND값이 0일 경우, XOR값은 1이 홀수개면 1, 짝수개면 0이다. 비트를 위에서부터 하나씩 보자. 어떤 비트에서 AND값이 처음으로 1일 경우 XOR값이 0이 되므로 그 아래 비트에서 값이 어떻게 나오든 무조건 (모든 값 AND) > (모든 값 XOR)을 만족한다. 따라서 "처음으로 AND값이 1인 비트"의 위치를 고정하면 그 위에서는 AND값과 XOR값이 모두 0, 그 아래에서는 어떤 값이든 상관 없으므로 식을 정리해보면 \( (2^{n-1} - 1)^k + \Sigma_{i=0}^{k-1} (2^{n-1} - 1)^i (2^n)^{k-1-i} \) 가 된다. AND값이 1인 비트가 없는 경우를 따로 고려해야 하므로 시그마 앞의 항이 필요함에 유의.

코드 : http://codeforces.com/contest/1557/submission/126746937

 

D

row 중 몇 개를 남기기로 했을 때, 인접한 두 row는 "둘 다 1인 column"이 적어도 하나 존재해야 한다. 우선 1이 적힌 구간들의 좌표를 압축해도 상관이 없으므로 대충 [0, 2M-1] 범위로 만들었다 치고, 길이 2M짜리 배열을 하나 잡자 (A라고 하자).

dp[i] : (1~i번째 row까지 고려했고, i번째 row를 마지막으로 남기기로 했을 때 최대로 남긴 row의 수) 로 정의하자. dp[i]는 결국 j < i인 dp[j]들 중 하나의 값에 1을 더한 것인데, 값을 얻어온 j번째 row는 i번째 row와 겹치는 1의 구간이 있어야 한다. 각각의 j에 대해 (j번째 row에 있는 1의 구간)에 해당하는 모든 k에다가 A[k]에 dp[j]의 값을 업데이트해놓았다고 하자. A[k]에는 그 자리에 적힌 dp값들 중 최대를 저장해 놓는다. 그러면, dp[i]를 계산할 때에는 (i번째 row에 있는 1의 구간)에 들어있는 모든 k에 대해 A[k]의 최댓값을 구하고 거기에 1을 더하면 된다.

앞에서 말한 과정을 그대로 구현하면 O(NM)인데, "[l, r] 구간에 A[x] = max(A[x], v) 업데이트하기 / [l, r] 구간에서 A[x] 최댓값 구하기" 는 Lazy Propagation을 사용한 세그먼트 트리로 연산당 O(logM) 시간이 걸리도록 최적화할 수 있다. 이를 구현하면 O(M+NlogM) 시간이 걸린다.

Div2D에 Lazy Propagation Segment Tree라니.. 세상이 미쳐 돌아간다.

코드 : http://codeforces.com/contest/1557/submission/126747845

 

E

일단 내 접근 방식은 "킹이 있는 위치의 경우의 수를 줄이자" 였다. 처음에는 킹이 있을 수 있는 곳이 여러 군데 있지만, 적절히 퀸을 옮겨 줌으로써 그 경우의 수를 줄여 나갈 수 있고, 최종적으로 그 위치가 1개로 확정이 된다면 그 때부터는 킹을 구석으로 몰아가는 전략을 사용할 수 있다.

킹이 있을 수 있는 자리 중 하나에 퀸을 바로 옮길 수 있다면, 그 곳으로 옮겨서 경우의 수를 줄일 수 있다. 그런 곳이 없을 경우가 문제인데, 잘 모르겠어서 일단 그 때는 랜덤으로 움직이도록 했다.

킹의 위치가 확정되면, 그 때부터는 킹을 구석탱이까지 몰고 가면 된다. 킹의 위치로 바로 갈 수 있다면 바로 가면 되고, 그렇지 않다면 케이스가 두 가지이다.
(1) 킹의 위치가 "나이트 한 번 움직임"으로 갈 수 있는 경우 : 대각선으로 한 칸 움직여서 킹 바로 옆 칸으로 가면 된다. 다음 턴에 킹이 어떻게 움직이든 킹의 위치로 갈 수 있다.
(2) 킹이 그것보다 멀리 떨어져 있는 경우 : 가로 / 세로 각각 독립적으로, 킹과 내가 2칸 이상 떨어져 있으면 해당하는 축에서 한 칸 가까이 가면 된다.

솔직히 틀릴 줄 알고 냈는데 맞아서 상당히 어이가 없었다. 틀리게 할 수 있을 거 같은데...

+ Editorial에 이런 댓글이 있다.

ㅋㅋ... 참고로 -237 받은 저 사람이 세터다.

코드 : http://codeforces.com/contest/1557/submission/126750319

'알고리즘 > 온라인 대회' 카테고리의 다른 글

Codeforces Deltix Round, Summer 2021  (0) 2021.09.05
제 3회 소프트콘 후기  (0) 2021.08.29
2020 ICPC Asia Macau Regional Contest  (0) 2021.08.21
Codeforces Round #736  (0) 2021.08.20
Codeforces Good Bye 2020 후기  (0) 2021.01.07