엘릭시르제

문제 풀이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 \..

문제 링크: https://www.acmicpc.net/problem/19124문제 풀이정수론 설명은 정말 간단한 문제. ${}_{n}C_{k} \bmod 2^{32}$를 구하면 된다.$2^{32}$는 매우 큰 수이기도 하고, 합성수여서 뤼카 정리를 사용하기에도 빡세보인다. 먼저 가장 쉬운 판별을 해보자.${}_{n}C_{k} = 2^E \cdot U$로 나타낼 때 $E \geq 32$이면 나누어떨어지므로 $U$를 계산할 필요가 없어진다. 이 $E$를 구하는 방법이라면 Legendre's formula를 이용해도 좋고 어렵지 않다. 다만 $p = 2$의 경우에는 $\nu_{2}(n!) = n - s_2(n)$($n$을 이진수로 나타내었을 때 $1$의 개수)로도 나타낼 수 있으니, $\nu_{2}({}_{..