엘릭시르제

매내처는 어떤 문자열 $S$에 대해 모든 위치를 중심으로 하는 가장 긴 팰린드롬 부분 문자열의 길이를 $O(|S|)$에 구할 수 있습니다. 하지만 매내처는 이해하기 까다롭고 생각하고 하는 일이 명확하다보니 이 알고리즘이 대회에 나오는 빈도가 낮습니다. 따라서 충돌만 피할 수 있으면 어떤 부분 문자열 $S'$이 존재하는지 빠르게 파악하는 해싱을 이용하여 가장 긴 팰린드롬 부분 문자열이 있는지, 그리고 그 길이가 최대 몇인지 알아보겠습니다. 먼저, 여기서 말하는 문자열에서 해싱은 롤링 해시을 이용한 라빈-카프를 의미합니다. 여기서는 매내처를 대체하는 방법에 대해서만 설명하겠습니다. 그리고 이 문서는 모두 1-based index로 작성되었습니다. 문자열 $S$가 있습니다. 그리고 $S$를 뒤집은 문자열 $R..

문제 풀이A. Robot Balance (1:04)구현 넘어지지 않게 하기 위해서 몸통 부분의 무게를 머리 부분의 무게보다 크거나 같게 만들자. 원래부터 컸으면 추가할 필요 없으니 0이고, 아니라면 같게 만들기 위해 $H-B$을 추가하면 된다. 코드 B. Robot Weight (3:57)구현 장착되어 있는지 아닌지에 대한 배열을 하나 만들어주고 0으로 초기화한다. 장착되어 있으면 $w[i]$를 빼고 0으로 바꾸고, 장착되어 있지 않으면 $w[i]$를 더하고 1로 바꾼다. 이러면 쿼리에 대한 답을 $O(1)$로 할 수 있다. 코드 C. Robot Factory (10:15) (+1)정렬, 그리디 $H_i \leq B_j$를 만족하는 $(i, j)$를 찾으라는 의미인데 순서는 임의로 변경해도 되므로..

문제 풀이최대 유량 문제는 단순하다. 격자판에서 WIN을 총 몇 개 만들 수 있는지 구하는 것인데, S -> W를 연결하고, N -> T에 연결한 다음에 I의 경우에는 W -> I, I -> N을 연결하면 된다. 하지만 이렇게만 하면 틀린다. I는 단 한 개 사용해야 하기 때문이다.이런 경우가 바로 틀리게 되는 원인인데, I는 1개 밖에 없지만 WIN을 2개 만들 수 있기 때문이다. 이를 방지하기 위해서는 간단하게 I에 대해 정점 분할을 해서 단 한 개의 I에만 유량을 흘리게 하면 된다. 여담으로 이 문제의 입력이 좀 귀찮은 편이다. 코드

문제 링크: https://www.acmicpc.net/problem/14317문제 풀이정수론, 포함 배제의 원리, 분할 정복을 이용한 거듭제곱 $N \leq 10^{18}$인 $i$, $j$가 있을 때 $(i^{A} + j^{B}) \pmod K = 0$와 $i \neq j$를 만족하는 순서 쌍 ($i$, $j$)의 개수를 구하는 문제이다. 굳이 위에 $10^{18}$을 언급하는 이유는 나이브한 $O(N^{2})$ 풀이는 쳐다도 볼 수가 없다는 뜻이다. 여기서 주목해야 하는건 $K$의 범위다. $10^{5}$보다 작거나 같으므로 이를 이용해보자. 먼저, '$N$보다 작거나 같은 $i$가 $K$로 나누었을 때 나머지가 $r$인 값은 총 몇 개 있는가?' 라는 해답부터 생각하면 된다. 당연하겠지만 $0 \..