처음으로 codechef에 가입하고 대회를 쳐보았다. 처음에는 Div 4.에서 치라길래 싱글벙글 빨리풀고 잘 생각으로 쳤는데, 생각보다 오래걸렸다;; 시간 남으면 Div 4. 이외의 문제들도 풀어보려고 했는데, 한 문제에서 너무 시간을 많이 잡아먹어서 Div 4. 문제만 푸는 선에서 마쳤다.
Candy Division
\(N\)을 입력받아 3으로 나눈 나머지가 0이면 YES, 아니면 NO를 출력하라는 문제이다. 그냥 하면 된다.
Reach Home
\(x, y\)를 입력받아 \(5x \ge y\)이면 YES, 아니면 NO를 출력하라는 문제이다. 역시 그냥 하면 된다.
Min To Max
길이가 \(N\)인 배열 \(A\)가 주어진다. \(A\)의 minimum 값을 \(M\)이라 할 때, \(A\)의 maximum 값이 \(M\)이 되도록 하기 위해 바꾸어야 하는 \(A\)의 원소의 최소 개수를 구해야 한다.
min_element 함수를 이용하여 \(A\)의 minimum 값을 찾고, \(A\)에서 \(M\)이 아닌 원소의 개수를 출력하면 된다.
Make A-B Same
길이가 \(N\)이고 0과 1로 이루어진 두 배열 \(A\)와 \(B\)가 주어진다. 이제 \(A\)에 아래 연산을 0회 이상 적용할 것이다.
\(1\le i < j < k \le N\)인 \(i, j, k\)를 고른 뒤, \(A_j= A_i | A_j | A_k\)를 대입한다.
위 연산을 0회 이상 적용하여 배열 \(A\)를 배열 \(B\)로 바꿀 수 있는 지 출력해야 한다.
맨 먼저 \(A\)가 모두 0인 경우는 예외처리를 해두자. \(A\)가 모두 0이면 그 어떤 원소도 1로 만들 수 없으므로 \(B\)가 모두 0이면 YES, 아니면 NO를 출력하면 된다.
이제 \(A\)에 1이 하나 이상 있다고 가정하자. 그렇다면 문제의 주어진 연산을 적용하면 index가 2이상 \(N-1\)이하인 원소를 1로 만들 수 있다. 하지만 1인 원소는 어떻게 해도 0으로 만들 수 없다. 따라서 \(B\)에서는 0인데, \(A\)에서는 1인 값이 있으면 NO가 되고, 또한 \(A[1]\)과 \(A[N]\)은 0일 때, 1로 바꿀 수 없으므로 \(A\)와 \(B\)의 첫 번째 원소나 마지막 원소가 다를 때도 NO가 된다. 그 이외에는 YES가 된다.
Difference Matrix
\(N\times N\) 행렬에 1부터 \(N\times N\)까지의 자연수를 채워넣을 것이다. 이때, 이웃하는 원소의 차이가 항상 2 이상이 되게 채워야 한다. 입력으로 주어지는 \(N\)은 4 이상의 자연수이다.
\(N\)이 5 이상인 경우 첫 번째 행을 1이상 \(N\) 이하의 수로 채우는 방법을 생각해보자. 이는 단순히 \([1, 3, 5, .... 2, 4, 6, ...]\)와 같이 홀수를 쭉 채우고 그다음 짝수를 채우는 방법으로 채울 수 있다. 두 번째 행은 첫 번째 행을 복사한 뒤에 모든 원소에 \(N\)만큼 더하면 된다. 마찬가지로 세 번째 행도 두 번째 행을 복사하고 모든 원소에 \(N\)을 더하면 된다. 이렇게 쭉쭉 행렬을 채워주면 된다.
하지만 \(N = 4\)인 경우에 첫 번째 행이 \([1, 3, 2, 4]\)가 되어 이웃한 숫자의 차이가 1이 된다. 그런데 이 문제의 예제에서 \(N=4\)일 때의 정답을 제공했으므로;; \(N = 4\)라면 그냥 예제를 출력하도록 했다.
Find eX
\( (A+X) \mod B = (C+X) \mod D\)를 만족하는 가장 작은 자연수 \(X\)를 구해야 한다. 이때, \( A \mod B = C \mod D \)를 만족한다.
일단 편의를 위해 \(A\)와 \(C\)를 \(A = A \mod B, C = C \mod D\)를 대입하고 계산을 시작하자.. 그러면 문제의 조건인 \( A \mod B = C \mod D \)에 의해 \( A = C\)가 될 것이다. 또한 편의상 \(B < D\)라 하자. 그렇다면 \(A + 1\ne B\)이라면 위 식을 만족하는 가장 작은 자연수는 \(X = 1\)이 된다. \(A + 1\)과 \(C + 1\) 모두 \(B, D\)보다 작아서\( (A+1) \mod B = (C+1) \mod D = A+1 \)이 되기 때문이다.
하지만 \(A + 1=B\)이라면 조금 더 생각해봐야 한다. \( (A+1) \mod B = 0\)이 되어버리기 때문이다. 이 경우에는 두 식을 만족하는 \(X\)값을 구했을 때, \(A+X \mod B = C+X \mod D = 0\)을 만족해야 한다. 만약 \(A+X \mod B = C+X \mod D = k\) 라면 \(X - k\)라는 값도 위 식을 만족하면서 \(X\)보다 작기 때문이다.
즉 가장 작은 자연수 \(X\)에 대해 \(A + X\)는 \(B\)의 배수이면서 \(D\)의 배수이어야 한다. 두 수의 배수이면서 가장 작은 수는 최소공배수이므로, \(B\)와 \(D\)의 최소공배수를 구하면 이 값이 곧 \(A + X\)가 된다. 따라서, 우리가 원하는 가장 작은 \(X\)는 \( \text{lcm}(B, D) - A\)가 된다. 여기서 \( \text{lcm}(B, D)\) 은 당연하게도 \(B\)이상일 것이고, \(A\)는 \(B\) 미만이니 \( \text{lcm}(B, D) - A\)는 항상 양수임이 보장된다.
Make Them Alike
길이가 \(N\)인 배열과 자연수 \(M\), 그리고 길이가 \(N\)인 permutation \(P\)가 주어진다. 각 \(A_i\)는 1이상 \(M\)이하의 자연수이며 매 \(i\)번째 단계에 \(A_i = A_{Pi}\)를 대입한다. 단계는 1단계부터 \(N\)단계의 순서로 진행된다.
그런데 일부 \(A_i\)들은 0값을 가지고 있다. 이는 \(A_i\)의 값이 정해지지 않아서 1이상 \(M\) 이하의 자연수로 할당할 수 있다는 뜻이다. \(N\)단계 까지 모든 단계를 거친 후 모든 자연수가 동일하도록 하고 싶다. 모든 자연수가 동일하도록 \(A_i=0\)인 값들에 1이상 \(M\)이하의 자연수를 할당할 때, 할당할 수 있는 경우의 수를 계산해야 한다.
사실 이는 생각보다 쉬운 문제이다. 일단 \(A_i = 0\)인 값들을 \(M + i\)로 바꿔두자. 그리고 이 상태에서 1단계부터 \(N\)단계까지 순서대로 실행한다. 이제 \(A_i\)의 값들을 확인해보자. 만약 \(M\)이하이고 서로 다른 두 숫자가 있다면, \(A_i = 0\)인 값들을 어떻게 배열해도 모두 똑같아질 수 없다는 것을 의미한다. 따라서 \(M\)이하인 값들이 모두 \(k\)로 동일하다고 가정하자. 이 경우에는 \(A_i = 0\)인 값 중 일부는 무조건 \(k\)로 바꿔야 할 것이고, 일부는 어떤 숫자로 바꿔도 상관없을 것이다. 이는 \(A_i\)의 배열을 확인해서 알 수 있다. 만약 \(A\)배열에 \(M + i\)값이 있다면, 해당 \(A_i\)는 무조건 \(k\)로 바꿔야 함을 의미한다. 따라서 맨 처음에 \(A_i=0\)이었으면서 \(M+i\)가 최종 배열에 없다면 해당 원소는 아무 값을 대입해도 된다. 따라서 이러한 원소의 개수를 \(n\)이라 하면 가능한 경우의 수는 \(n^M\)개가 있다.
여기서 문제를 마무리하면 틀렸습니다를 받게 될 것이다. 만약 \(N\)단계를 모두 거쳤는데, \(M\)이하인 값들이 하나도 없는 경우에는 동일하게 만들 \(k\)값 또한 원하는 값으로 선택할 수 있다는 것을 의미한다. 따라서 이 경우 최종 정답에 \(M\)을 곱해서 문제의 답을 최종적으로 구할 수 있다.
Good Permutation
div 4. 대회의 보스 문제이다. 약 18,000명 중 대회 종료까지 나 포함 단 2명만 풀었다... 심지어 이 문제를 푼 한 명은 다른 문제를 풀지 못해서 모든 문제를 푼 사람은 나밖에 없었다. 나도 구현 이슈 등으로 이 문제에서 거의 2시간은 쓴 거 같다.
길이가 \(N\)인 두 배열 \(A\)와 \(B\)가 주어진다. \(B\)를 재배열하는 방법은 총 \(N!\)가지가 있을 것이다. 이제 재배열한 \(B\)가 아래 조건을 만족하면 good이라고 한다.
1. 길이가 \(N\)인 배열 \(C\)에 대해 \(C_i = A_i + B_i\) 또는 \(C_i = A_i - B_i\)를 만족해야 한다.
2. \(C\)의 모든 원소가 동일해야 한다.
이제 \(N!\)종류의 재배열된 \(B\) 중에서 good인 배열의 개수를 구해야 한다.
이 문제는 그냥 어렵다. 관찰도 어렵고 구현도 어렵고 edge case를 찾아서 없애는 것도 어려웠다. 사실 졸린 데에다 멘탈도 살짝 깨진 영향도 있겠지만 그걸 고려해도 어려운 문제였다.
일단 \(B\) 배열을 더하거나 뺄 수 있다는 거 자체가 어렵다. 두 가지 경우를 고려해야 하기 때문이다. 따라서 \(B\) 배열에서 \(A\) 배열을 더하는 방향으로 생각해보자. 이렇게 생각하면 그나마 쉬워진다. 그리고 어짜피 \(B\)의 원소를 뺴거나 더하기 떄문에 \(B\)의 원소에 절댓값을 씌워도 답은 변하지 않는다. 따라서 절댓값을 씌워버리자.
배열 \(C\)를 만드는 방법을 생각해보자. 먼저 어떤 값으로 통일시켜야 하는 지를 생각하면 좋다. \(B\) 배열에서의 가장 큰 값을 \(b\)라고 하자. 결국 이 원소로 배열 \(C\)의 값을 만들 것인데 \(A\)의 어떤 원소에서 \(b\)를 더하거나 빼서 만들 것이다. 일단 \(n\)를 더하는 경우를 고려해보자. 배열 \(C\)를 만들 때, 이 \(b\)에는 \(A\)의 가장 작은 원소에 더해져야 할 것이다. 만약 \(b\)에 \(A\)의 어떤 원소를 더했는데 이보다 작은 원소인 \(a\)가 존재한다고 하자. 그렇다면 이 \(a\)에는 배열 \(B\)에서 \(b\)보다 큰 값을 더해줘야 \(C\)의 모든 원소의 값이 똑같을 것이다. 하지만 \(b\)는 가장 큰 값이라고 했으므로 이는 모순이다. 마찬가지로 \(b\)를 뺄 때에는 \(A\)의 가장 큰 원소에서 빼줘야 할 것이다.
그렇다면 통일시킬 수 있는 값이 최대 2개임을 알 수 있다! 이는 매우 중요한 정보로, 배열 \(C\)를 \(k\)라는 값으로 통일시킬 수 있는지를 \(O(N)\)에 검증할 수 있다면 이 문제를 풀 수 있다. 실제로, \(O(N)\)에 배열 \(C\)를 \(k\)로 통일시킬 수 있는지 검사할 수 있다. 단순하게 \(A\)의 각 원소에서 \(k\)를 뺀 다음에 이 배열이 \(B\)와 같은지를 보면 된다. 이를 \(k=\max A - \max B\), \(k=\min A + \max B\)에 대해서 검사해주면 된다.
이제 재배열할 수 있는 경우의 수를 출력해야 한다. 이는 단순하게 \(B\)에 같은 값들이 있다면 이 값들끼리는 순서를 바꿔도 상관없다. 따라서 배열 \(B\)에 동일한 값이 \(b1, b2, ...\)개 있다면, 단순하게 \(b1! \times b2! \times ...\)를 계산해주면 된다.
따라서 통일시킬 수 있는 값 개수에서, \(b1! \times b2! \times ...\)를 곱해주면 답이 나오게 된다... 면 좋겠지만 여전히 하나의 예외 처리를 해야 한다. 놀랍게도 두 개의 \(k\)값에 대해서 배열 \(B\)를 만들었는데, 두 배열 \(B\)의 순서가 완전히 동일할 수가 있다. 따라서 두 개의 \(k\)값에 대해서 처음 배열 \(A\)에 대해 배열 \(B\)을 어떻게 재배열해야 하는 지 저장해두고, 만약 두 \(k\)값에 대해 배열이 똑같다면 통일시킬 수 있는 \(k\) 값이 2개더라도 가능한 배열은 1가지이기 때문에 경우의 수를 둘이 아닌 하나로 취급해야 한다. 이렇게 열심히 구현하면 AC를 맞게 된다.
후기
위풍당당하게 올 솔브로 div 4 1등을 차지했다. 빨리 레이팅 올려서 높은 div에서 경쟁해보고 싶다는 생각이 든다.
codechef에는 사람이 별로 없을 줄 알았는데 무려 18,000명 정도로 꽤 많은 수의 사람들이 있었다. 그런데 순위권을 보니 대부분이 인도 사람이라, 인도 인구 수를 생각하면 그럴수도 있겠구나 하는 수준의 사람 수였다. 3시간 대회였고, 실질적으로 어려운 문제는 뒤에 세 문제 정도라 올솔브가 꽤 있을만도 한데 없다는 게 조금 놀라웠다. div 4라 그런 거 같기도 하다.
대회가 div 1부터 div 4까지 있고, div 1에는 세 문제가 추가로 있는 것으로 보아 div 1에서는 이런 식으로 말리면 망했을 것 같다;; 그와는 별개로 은근 문제의 퀄리티가 좋았다. 너무 뻔하지 않으면서 참신한 문제들이라는 생각이 들었다. 매 주 수요일 저녁마다 있는 거 같던데 시간 된다면 계속 칠 것 같다.