나름 개발자의 IT블로그

백준에 순열 사이클 분할(permutation cycle decomposition)이라는 태그가 있어서 공부를 하게 되었다. 기본적인 개념은 다음과 같다. 어떤 순열 $(a_1, a_2, \dots , a_n)$이 있으면 $a_i = f(i)$인 함수가 있다고 생각해보자. $f^2(i) = f(f(i))$라고 할 때 $i = f^k(i)$인 $1 \le k \le n$을 찾을 수 있다. 그럼 $k$번 연산하는 과정에서 나온 수들을 모으면 $(f(i), f^2(i), \dots, f^k(i))$가 나올 것이고 이것을 하나의 순열 사이클이라고 한다. 순열 사이클 안에 존재하는 원소들은 모두 같은 순열 사이클이 될 것이다. 모든 원소에 대해 수행하면 여러개의 순열 사이클이 나오는데 이를 구하는 것을 순열 사이..

이번에 4솔을 하여 민트로 복구할 수 있었다. 코드포스가 있던날 백준, 앳코더도 함께 진행해서 좀 힘든하루였다.(백준 4시간, 앳코더 1시간, 코드포스 2시간..) A - Min Or Sum [Solved!] 배열 $a$에서 서로 다른 원소 $a_i, a_j$를 뽑아 $a_i|a_j = x|y$를 만족하면서 $a_i = x, a_j = y$인 연산을 반복할 때 가능한 배열의 합의 최솟값을 찾는 문제이다. $x = a_i|a_j, y = 0$으로 두면 위 조건을 만족한다. 이 연산을 반복해서 하나의 원소에 적용하면 결국 배열은 $a_1|a_2| \dots | a_n, 0,0, \dots , 0$모양이 될 것이다. 이 때가 최소가 된다. B - Avoid Local Maximums [Solved!] 배열의 ..

민트를 복구할 수 있는 기회였는데 아쉽게 실패하고 말았다. 3솔에 블루퍼포가 나와서 싱글벙글하고 있었는데 B가 TLE로 터져버렸다. 알고보니 sys.stdin.readline을 쓰지 않아 생긴 문제였다. C문제도 같은 이유로 프리테스트에서 TLE가 발생했지만 B에서도 나올줄은 전혀 몰랐다. (두 문제 모두 $O(n)$으로 해결했었다.) 앞으로는 확인을 꼼꼼히 해야겠다. (후에 라인 추가로 AC받긴 했다.) A - Reverse [Solved!] 배열의 중간 일부 구간을 뒤집었을 때 사전순으로 가장 앞서는 배열을 출력하는 문제이다. 인덱스와 배열값이 다른 부분이 나오는 곳부터 그 이후에 나오는 최솟값이 있는 곳까지 뒤집으면 된다. B - Odd Swap Sort [Solved?] 배열에서 연속한 두 원소의..

이번에 본대회를 참가할 수 없어서 버추얼에 참가했다. A - Sorting Parts [Solved!] 길이가 $n$인 배열이 주어질 때 $1\le i\le n-1$를 정해 $[a_1,\dots,a_i], [a_{i+1},\dots,a_n]$를 정렬하여 이어붙일 때 내림차순이 아닌 배열을 만들 수 없는지 묻는 문제이다. (오름차순이 아닌 배열을 만들 수 있는지 묻는 문제) 주어진 배열이 이미 오름차순이라면 내림차순이 아닌 배열(오름차순)을 만들 수 있다. B - MEX and Array [Solved!] 배열을 $k$개의 구간으로 적당히 나누어 $ cost = c+\sum_{i=1}^c mex(\{ b_{l_i}, b_{l_{i+1}}, \dots, b_{r_i}\}) $ 라고 하자. 배열의 모든 부분배..

이번 코드포스의 결과는 굉장히 참담했다. 그래서 다시 그린으로 내려왔다. A - Reverse and Concatenate [Solved!] 문자열이 주어졌을 때 다음 연산을 $k$번 하여 만들 수 있는 서로 다른 문자열의 수를 구하는 문제이다. 연산은 다음중 하나를 수행한다. - 문자열을 뒤집어 원래 문자열 앞에 이어 붙인다. - 문자열을 뒤집어 원래 문자열 뒤에 이어 붙인다. 우선 연산을 한 번이라도 수행하면 문자열은 팰린드롬이 된다. 또한 팰린드롬은 뒤집어서 어디에 이어 붙여도 같은 문자열이 된다. 결국 주어진 문자열이 팰린드롬인지 확인하는 문제로 환원된다. 다만 팰린드롬에 상관없이 $k=0$일 때는 답이 1이다. A번부터 뇌절을 심하게 해서 4번틀리고 AC를 받았다. (발상이 상당히 힘들었다.) ..

연습용으로 예전 Contest에 버추얼참가를 했다. 아쉽게도 4솔에 실패했다. A - Two Subsequences [Solved!] 문자열 $s$가 주어지고 그 문자열을 $a, b$인 두 개의 문자열로 나눌건데 $a$는 사전순으로 가장 앞서는 문자열, $b$는 $s$에서 $a$를 제외한 문자열인 조건이 있을 때 나눠진 문자열들을 출력하는 문제이다. $a$는 $s$에서 사전순으로 가장 앞서는 문자 하나이면 충분하다. 예를들어 $s = ``helloworld"$일 때 $a = ``d"$이고 $b =``helloworl"$이 된다. B - Divine Array [Solved!] 배열 $a$가 주어지고 그 배열에 연산을 여러번 하려고 할 때 $k$번 연산을 수행한 후 $x$번째 위치의 수를 묻는 문제이다. ..

버추얼에 참가했다. 이번 대회는 다른 대회보다 쉬웠던 것 같다. A - Div. 7 [Solved!] 정수가 하나 주어졌을 때 변화하는 자릿수를 최소로 하며 7의 배수로 만드는 문제이다. 7의 배수이면 그냥 출력하고 아니라면 1의 자리를 0~9까지 변화하면서 7의 배수가 되는 수를 출력한다. 자릿수를 하나만 변화시켜도 7의 배수를 만들 수 있다. B - Minority [Solved!] 이진문자열이 주어졌을 때 부분 문자열을 골라 0, 1중에 개수가 작은 문자를 전부 삭제한다.(같으면 무효) 이때 삭제한 문자의 수의 최댓값을 구하는 문제이다. 전체 문자열을 부분문자열로 선택하고 둘 중에 개수가 작은 문자의 수를 출력하면 된다. 만약 같은 경우는 갯수-1을 출력하면 된다. C - Kill the Monst..

이번에 처음으로 Div.2 에서 3솔을 하고 민트를 갔다! 당분간 3솔이 편해질때까지 버추얼만 참가할 예정... A - ABC [Solved!] 이진 문자열의 부분문자열 중 길이가 2이상인 팰린드롬이 있는지 찾는 문제이다. 보자마자 매내처생각나서 제출하고 AC를 받았다. 끝나고 생각해보니 그냥 부분문자열 길이 2이상 3이하인 팰린드롬 찾아도 풀 수 있었다. B - Roof Construction [Solved!] $n$이 주어졌을 때 배열 $(0,1,2,..., n-1)$의 순열중 인접한 xor값의 최댓값을 최소로 하는 배열을 찾는 문제이다. 접근방법이 도저히 생각안나서 C풀고 온 후 남은 90분 B풀고 끝낼 생각으로 천천히 풀었다. 우선 $n=2$~$10$까지 모든 순열에 대해 xor값의 최댓값을 구했..

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다. (푸는대로 업데이트 할 예정..) A. 2의 보수 정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다. 입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음) B. 조커 찾기 카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다. - 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다. - 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다. 문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는..

코드포스에 너무 어려움을 느껴 앞으로 editorial를 보고 공부하여 블로그에 정리하고자 한다.. (Div2 2솔까지는 할만한데 3솔부터 못해먹겠다.) A - min max swap [Solved!] 두 배열 $a_1, a_2, ... , a_n$과 $b_1, b_2, ..., b_n$이 주어졌을 때 같은 인덱스들을 여러번 적절히 바꾸어 만들어진 새로운 두 배열을 만든다. 만들어진 각 배열의 최댓값을 곱했을 때 가능한 최솟값을 구하는 문제이다. $a_i, b_i$를 비교하면서 두 수중 작은 값을 $a_i$, 큰 값을 $b_i$에 넣으면 최적해가 구해진다. B - Fun with Even Subarrays [Solved!] 배열이 주어졌을 때 적당한 범위 $a_l, a_{l+1}, ..., a_r$을 정..