Atcoder Regular Contest 164

23년 7월 9일 진행한 ARC164 대회 일지입니다. 시험 끝나고 첫 대회였는데(노느라 ABC309에 참가하지 않았습니다), 확실히 2주 정도 CP를 쉬니까 문제가 잘 안 풀리는 것 같습니다.

0:00~0:04

• A번 Ternary Decomposition을 잡았습니다.
• $N$을 $K$개의 3의 거듭제곱수로 나타내는 문제였습니다.
• $N$을 3개의 거듭제곱수로 나타내려면 적어도 $N$을 3진법으로 표현할 때 필요한 만큼의 3의 거듭제곱수가 필요합니다.
• 이를 $M$이라 두면, $K$-$M$이 양의 짝수이거나 0이면 문제를 해결할 수 있습니다. ($3^r = 3 * 3^{r-1}$이므로, $N$을 $K$개의 수로 나타낼 수 있다면 자명히도 $K+2$개의 수로도 표현 가능합니다.)

  아이디어에 2분, 구현에 2분 소요했습니다.

0:04~0:18

• B번 Switching Travel을 잡았습니다.
• 무향 연결그래프에서 특정 조건을 만족하는 홀수 크기 사이클을 찾는 문제였습니다.
• 처음 아이디어를 틀리게 잡았고(훨씬 더 쉬운 코포식 발상 문제로 보았습니다) 15분 정도를 사용했습니다.
• 못 풀고 C로 넘어갔습니다.

0:18~0:56

• C번 Reversible Card Game을 잡았습니다.
• 카드에 적힌 두 수의 크기는 중요하지 않고, 두 수의 차이만을 가지고 고르기와 뒤집기를 지행하면 됩니다.
• 아이디어 1: 어차피 밥은 두 수 중 작은 수만큼의 점수는 무조건 얻을 수 있습니다. (이 발상은 비교적 빠르게 잡았습니다.)
• 아이디어 2: 따라서 앨리스 입장에서는 (윗면 - 아랫면)값이 가장 큰 카드를 뒤집으면 되고, 밥은 (윗면 - 아랫면)값이 가장 큰 것을 고르면 됩니다. (이건 구체화하는 데 시간이 조금 많이 걸렸습니다.)
• 우선순위 큐를 이용하면 쉽게 구현할 수 있습니다.

  아이디어 1에 10분, 틀린 구현에 9분, 디버깅에 7분, 아이디어 2에 5분, 구현에 7분 정도를 사용했습니다.

0:56~1:20

• B를 다시 잡았습니다.
• ‘무향 연결그래프에서 특정 조건을 만족하는 홀수 크기 사이클을 찾는 문제’라는 사실을 알아냈습니다.
• 이를 빠르게 할 수 있는 방법을 몰랐고, 포기했습니다.

1:20~2:00

• 백준 스트릭을 채우고 잤습니다.

B 풀이

• 같은 색의 두 정점 사이를 잇는 간선과 다른 색의 정점 사이를 잇는 간선을 따로 관리합니다.
• 다른 색의 정점 사이를 잇는 간선으로만 이루어진 연결 요소에서, 연결 요소 내의 동일한 색을 가진 임의의 두 정점 사이의 간선이 존재한다면 Yes입니다.
• 따라서 유파 + 관찰 문제입니다.
• 풀이를 보면 할 만한 관찰이라는 생각도 듭니다. 확실히 문제를 잘 관찰하는 연습이 더 필요할 것 같습니다.

후기

• 켄쿠에 B와 C가 같은 난이도로 나왔습니다. 마음이 약간 아팠습니다.
• 레이팅은 떨어졌습니다.
• 정올 2차가 1주일 남아서 PS 재활이 필요합니다. 이제 셋을 최대한돌아볼 생각입니다. 그리고 가능하다면 풀이도 올리고요.