와 마지막 코드포스 대회로부터 1년도 더 됐다.
A: Make It Zero
원래 div 2 A 문제가 이렇게 어렵던가?
숫자들이 주어졌을 때 연속된 범위로 묶어 XOR 처리한 이후 그 결과로 해당 범위의 모든 수를 덮어씌우는 연산을 최대 8번 수행해서, 모든 수를 0으로 만드는 방법을 찾아야 한다.
숫자의 개수가 짝수일 때는 모든 숫자에 해당 연산을 두번 반복하면 모두 0이 된다.
숫자의 개수가 홀수일 때는 모든 숫자에 해당 연산을 수행한 이후, 마지막 숫자를 제외한 짝수개의 숫자에 연산을 적용해 모두 0으로 만들어준 이후, 마지막 숫자와 그 직전 숫자(이제 0이다) 두 숫자에 대해 연산을 두번 반복해주면 된다.
AC: 9 분
B: 2D Traveling
평면 위에 도시들이 있다. 특정 도시들은 '주요 도시'이며 출발지와 목적지가 모두 '주요 도시'인 이동은 무료이다. 나머지 이동들은 두 도시 사이의 택시거리만큼 비용이 발생한다. 출발 도시와 목적지 도시가 주어질 때, 최소비용 경로를 구해야 한다.
1. 최종 목적지로 직행하는 경우
2. 출발지와 가장 가까운 '주요 도시'로 이동한 이후 목적지와 가장 가까운 '주요 도시'로 이동한 후, 최종 목적지로 가는 경우
이렇게 두 가지만 비교해주면 된다.
AC: 19 분
오랜만에 보는 MEX였다. MEX는 Minimal Excluded Value이다. 0, 1, 2, 4의 MEX는 3.
행렬의 크기가 주어지면, 행렬의 각 row들을 permutation들로 채워서, 각 column의 MEX값들의 MEX값을 최대화해야 한다.
생각해내는데 조금 시간이 걸렸지만,
. 0 1 2 3
. . 0 1 2
. . . 0 1
. . . . 0이런 형태의 구조를 행렬 안에 집어넣고 왼쪽 column부터 순서대로 0, 1, 2, 3, 4가 나타나지 않도록 배열하면 된다.
즉 다음처럼 하면 된다:
4 0 1 2 3
3 4 0 1 2
2 3 4 0 1
1 2 3 4 0남아도는 row가 있다면 그냥 아무 다른 row나 반복하면 된다.
AC: 48 분
D1: Candy Party (Easy Version)
사람들 사이에 2의 거듭제곱 개수의 사탕을 주고받아 모든 사람이 가진 사탕의 수가 같아지도록 만들 수 있는지 확인해야 한다.
단 모든 사람은 정확히 한명에게로부터 사탕을 받고 한명에게 사탕을 주어야 한다.
모든 사람이 최종적으로 같은 개수의 사탕을 가져야 하므로, 최종 목표치를 달성하기 위해 각 사람이 몇개의 사탕을 얻어야(잃어야)하는지 알 수 있다. 이 숫자를 $2^x-2^y$로 나타내는 방법은 유일함을 쉽게 보일 수 있다.
모든 사람에 대해 이 $x$와 $y$를 구해서, 주는 사탕의 수와 받는 사탕의 수 조합이 일치하는지 확인하면 된다.
AC: 1 시간 8 분
D2: Candy Party (Hard Version)
이 버전에서는 최대 한명에게 사탕을 준다. 즉, 사탕을 안줄 수도 있다.
$2^x-2^y$ 말고도 그냥 $2^z$ 형태로 사탕을 얻을 수 있다는 것인데, 이게 가능한 사람들의 목록을 따로 추려서, 나머지 사람들의 사탕 수요를 맞춰주는 느낌의 풀이를 떠올려봤다. 사탕을 주는 사람의 수와 받는 사람의 수가 같아야 하므로 이 제약을 생각하며, 사탕을 주고받을 수 있는 두 형태 중 선택을 해서 모든 주고받음이 성사되도록 해야 하는데 어떻게 하는지 몰라서 대회가 끝났다 ㅎ
정해를 보니 내 접근법이 맞았다.
가장 큰 2의 거듭제곱을 요하는 사람부터 하나씩 두 방법 중 어느 방법을 택해야 하는지 결정할 수 있는 것 같다.
총평
아직 최종 결과가 나오지는 않았지만 현 시점 기준 1만여명 중 261등이다. 레이팅이 57정도 오를 것 같다.
그냥 무난하게 잘 한 것 같다. D2는 푼 사람이 186명인데, 안정적으로 div. 1에 진입하려면 이정도 문제를 꽤 안정적으로 풀어낼 수 있도록 노력해야 할 것으로 생각된다.
레이팅 변화: 1795 + 62 = 1857
My Performance: ★★★☆☆
연습지
