글 (510) 썸네일형 리스트형 [C++] 4442번 빌보의 생일 https://www.acmicpc.net/problem/4442 26/02/22 인버전 카운팅을 하는 문제다. 문제 접근 방식: 첫번째로 주어진 사람들의 목록에 번호를 매기자.문제에서 주어진 예시라면, Frodo에 $1$번, Sam에 $2$번, Bilbo에 $3$번을 매기는 것이다.두번째로 주어진 사람들의 목록을 매긴 번호로 치환한다. 문제의 예시라면 Sam Frodo Bilbo순으로 주어져있으므로, $2\ 1\ 3$으로 바뀐다.이후 바뀐 순열에 대해 인버전 카운팅 문제를 해결해주면 된다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 4442번 빌보의 생일// 자료 구조, 세그먼트 트리, 집합과 맵/*접근 방법:인버전 카운팅을 하는 문제다.첫.. [C++] 9463번 순열 그래프 https://www.acmicpc.net/problem/9463 26/02/21 인버전 카운팅을 하는 문제다. 문제 접근 방식: 첫번째로 주어진 순열이 $1\ 2\ 3\ \dots N$에 매핑된다고 간주하자.즉, 예제 입력 1의 첫번째 테스트 케이스를 예시로 들자면 $2\ 5\ 4\ 1\ 3$을 $1\ 2\ 3\ 4\ 5$로 간주하자는 뜻이다.즉, $2$를 $1$로, $5$를 $2$로, ... 그렇게 모든 수를 각각의 수로 간주하자.이후 두번째로 주어진 순열을 매핑된 수로 바꾸면, 주어진 순열에 대한 인버전 카운팅을 세는 문제로 바꿀 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 9463번 순열 그래프// 자료 구조, 세그먼트 트리 .. [C++] 28866번 Морти покупает продукты https://www.acmicpc.net/problem/28866 26/02/18 자주 나왔던 단골 유형의 FFT문제이다. 문제 접근 방식: $N$개의 수들 중 중복을 포함하여 $K$개를 선택했을 때의 가능한 경우의 수를 세는 문제라고 요약할 수 있다.이전에 너무 많이 했던 FFT문제 유형이다. 특히, 보석 가게 문제와 거의 유사하다고 볼 수 있다.실제로 필요한 다항식의 차수는 $50\ 000$까지 밖에 안되므로, 거듭제곱을 하며 중간 중간 크기를 resize해줘도 상관 없다.또한, 여기서 $786\ 433$이라는 특이한 수가 쓰이는데, 이 수는 $3\times 2^{18}+1$로 NTT-friendly한 소수이다. 원시근은 $10$을 사용하면 된다.이 점만 유의하여 구현하고, 나온 결과를 누적합을.. [C++] 29021번 IPvK https://www.acmicpc.net/problem/29021 26/02/17 자꾸 시간초과가 나서 애를 먹었던 문제이다. 문제 접근 방식: 우리가 원하는 요구 사항을 수학적으로 기술하자면 다음과 같다.- $a_{1} + a_{2}+\dots+a_{k} = N$- $0 \leq a_{i} \leq 255$- $\displaystyle \sum_{\begin{align}&a_{1}+\dots+a_{k}=N\\&0\leq a_{i} \leq 255\end{align}}\prod_{i=1}^{k} a_{i}$결국, 이걸 어떻게 구하냐가 문제다.우리는 지수의 합에서 $a_{1}+a_{2}+\dots+a_{k}=N$조건을 만족시킬 수 있음을 이전의 수 많은 FFT 문제들을 통해 확인해 왔었다.결국 곱이 .. [C++] 20340번 Lost Map https://www.acmicpc.net/problem/20340 26/02/16 FFT를 이용한 문자열 매칭 문제이다. 문제 접근 방식: 이전에 14958번 Rock Paper Scissors문제를 푼 적 있었는데 그거랑 매우 유사하고, 그거랑 비교했을 때 약간 한번 더 생각하면 풀리는 문제이다.일단 경우의 수가 4개가 있다.1. 두 문자 모두 ?가 아니고 서로 같음2. 두 문자 모두 ?가 아니고 서로 다름3. 두 문자 중 하나가 ?임4. 두 문자 모두 ?임우리가 구하고자 하는 것은 1번 + 3번 + 4번 경우이다.즉, 1번 + 3번 + 4번 경우가 $m$이라면 문자열이 매칭된다고 볼 수 있다.다른 말로, 2번 경우가 $0$이라면 문자열이 매칭된다고 볼 수 있다.'?'일때는 $0$, '?'가 아닐.. [C++] 30977번 금강산도 식후경 https://www.acmicpc.net/problem/30977 26/02/15 문제의 접근 방법이 그리 어렵지 않은 문제이다. 문제 접근 방식: 문제가 뭐라고 길게 쓰여있지만, 주어진 수를 중복 포함하여 여러번을 뽑아 합을 만드는 경우의 수를 구하는 문제로 귀결된다.이런 문제들은 우리가 이전에 정말 많이 해결했던 문제들이다.다항식 배열을 만들고 해당 배열을 $M$제곱하면 된다.문제를 잘 읽어보면 이제 문자열 매칭으로 넘어간다는 사실을 알 수 있다.인접한 $D_{i}$끼리의 차 배열과 인접한 $F_{i}$끼리의 차 배열을 만들어서 두 배열을 매칭으로 비교하면 된다.KMP를 써도 되고 라빈카프 써도 되는데, 나는 라빈카프로 했다.(바로 짤 수 있는게 그것뿐이어서...)여러 번 시행착오를 겪었다.2번.. [C++] 13278번 피보나치 합의 개수 https://www.acmicpc.net/problem/13278 26/02/14 꽤나 풀기에 까다로운 문제였다. 풀이 과정을 하나 하나씩 곱씹어보며 정리하고자 한다. 문제 접근 방식: 우리가 결국 원하는 것은 피보나치 수의 합을 $99991$로 나눈 나머지이다.($99991$은 소수다.)따라서 피보나치 수 하나하나를 $99991$로 나누어도 상관 없다.피사노 주기에 의하여, 피보나치 수들은 모듈로 $99991$에 대하여 어떤 주기를 가진다.실제로 파이썬으로 계산을 해봤고, 해당 주기는 $33330$이 나왔다.집합의 각 원소는 피보나치 수의 인덱스이므로, 집합의 각 원소들을 모두 $33330$에 대해 모듈로를 취해줄 수 있다는 사실 또한 확인할 수 있다.이제 우리가 구하고자 하는 것은 $N$개의 집.. [C++] 15050번 Laboratório de biotecnologia https://www.acmicpc.net/problem/15050 26/02/13 누적 합을 곁들인 쉬운 FFT응용문제이다. 문제 접근 방식: 문제를 번역해서 요약을 하자면 다음과 같다.먼저, 문자열 $S$의 가중치를 정의한다. 문자열 $S$의 가중치는, $S$를 이루고 있는 문자들의 가중치의 합으로 정의한다.여기서 문자의 가중치란, $a=1, b=2, c=3,\dots,z=26$으로 정의한다.우리가 구하고자 하는 것은 임의의 문자열 $S$가 주어질 때, $S$의 비어있지 않은 연속부분문자열 $s$가 가질 수 있는 서로 다른 가중치의 값이 모두 몇 개인지 구하는 것이다.일단 연속부분문자열 $s$의 가중치는 누적 합을 통해 $\mathcal{O}(N^2)$의 시간 복잡도로 모든 값을 구할 수 있다.하.. 이전 1 2 3 4 ··· 64 다음