Virtual Codeforces Round 956 (Div. 2)

시험이 끝난 날 Virtual Participation으로 참가한 코드포스 956번 대회 일지입니다.

0:00~0:02

• A번을 잡았습니다.
• 발상 1: 다 1으로 채우면 됩니다(틀렸습니다).
• 발상 2: 1, 2, 3, 4…로 채우면 됩니다(맞았습니다).

0:02~0:24

• B번을 잡았습니다.
• 말렸습니다.
• 발상 1: 크기 $nm$은 크기 $22$를 여러 번 해서 얻을 수 있으므로, 크기 $2*2$로 잘 만들면 됩니다.
• 발상 2: 그러면 사발 뒤집기처럼 왼쪽 위부터 쭉 밀면서 하면 됩니다.
• 맞았습니다.

0:24~0:34

• C번을 잡았습니다.
• 어차피 모든 칸을 채우는 것이 이득이므로, a-b-c, a-c-b, … 6개의 순서에 대해 채워지는 최소를 채우면 됩니다.
• 맞았습니다.

0:34~0:46

• D번을 잡았습니다.
• 관찰: 정렬된 상태에서 시작한다고 할 때, 어떤 배열은 홀수 번의 스왑으로 도달 가능하거나 짝수 번의 스왑으로 도달 가능하나, 둘 다는 불가능합니다.
• min swap sort를 구현해서 그것만 처리해주었고 맞았습니다.

0:46~1:01

• E번을 잡았습니다.
• 게임의 상황에 따라 기댓값을 계산할 필요 없이, 각 공이 누구에게 갈지의 확률을 기반으로 기댓값을 구하면 됩니다.
• 일반 공과 특별 공을 나누어서 생각할 때,
• 일반 공을 어떤 순서로 정렬하면 홀수 번째는 앨리스, 짝수는 밥이 가져갑니다.
• 이 정렬에 B를 중복조합 하듯이 꽂습니다. 이때 홀수 번째 공의 앞으로 들어가면 앨리스, 짝수 번째 공의 앞으로 들어가면 밥이 가져갑니다. 맨 마지막에 들어갈 경우 마지막 일반 공을 가져가지 않은 사람이 가져갑니다.
• 이를 기반으로 확률 놀이를 하면 됩니다.
• 맞았습니다.

1:01~1:20

• F번을 봤습니다.
• 포기했습니다.

후기

• B에서 말릴 때만 해도 확실히 PS 재활이 필요하겠구나 싶었는데, CDE를 생각보다 너무 쉽게 풀어내 버렸습니다. 그냥 했으면 2400 퍼포로 오렌지에 복귀했을 것 같습니다.