PS 일지 (241107-241210)

수학 위주로 좀 풀었다.

BOJ 17563 (Mona Lisa)

$N(\le 50)$비트 랜덤 정수열 $A$, $B$, $C$, $D$가 주어질 때, $A_i\oplus B_j\oplus C_k\oplus D_l=0$인 $(i,j,k,l)$을 찾는 문제이다. 각 정수열은 pseduo-random generator와 시드로 표현된다.

수열 4개를 동시에 다루는 것은 복잡하기 때문에 먼저 2개씩 묶어서 생각한다. 길이 $2^X$ 정도의 수열 2개를 합치면 상위 $X$비트가 0인 원소 $2^X$개 정도를 얻을 수 있다. 이렇게 하면 상위 $X$비트가 모두 0인 $2^{2X}$개의 페어를 만들 수 있고 이 중 하위 $N-X$비트가 겹치는 페어를 찾으면 된다. 따라서, $X=N/3$정도로 하면 풀 수 있고 이때 다루는 수의 개수는 대략 $2^{17}$개 정도이므로 시간제한 내에 풀 수 있다.

BOJ 31544 (K의 배수 Extreme)

$1$부터 $N$까지 적힌 공이 $M$개씩 있다. 같은 숫자가 적힌 공끼리는 색이 달라서 구분이 가능하다. $N$의 약수인 $K$가 주어질 때, 공을 1개 이상 뽑아 적힌 수의 합이 $K$의 배수가 되게 하는 경우의 수를 세는 문제이다.

생성함수로 접근하는 문제이다. 함수 $f(x)=(1+x{)}^M(1+x^2{)}^M\cdots (1+x^N{)}^M$을 생각해 보자. $x^K,x^{2K},\cdots$ 꼴의 항의 계수의 합을 구하는 것과 동치라는 것을 알 수 있다. $f$에 $e^{\frac{2\pi }{K}t}$를 대입해서 전부 더하면 차수가 $K$의 배수인 항만 남게 된다. $f(e^{\frac{2\pi }{K}t})$를 계산하는 것은 결국 어떤 적당한 $n$에 대해 $f(e^{\frac{2\pi }{n}})$을 계산하는 것과 동일하다. $n$이 짝수일 경우, $(1-1)$항이 존재해서 $0$이 된다. $n$이 홀수일 경우, $w=e^{\frac{2\pi }{n}}$라고 할 때 $(1+w)(1+w^2)\cdots (1+w^{n-1})=1$이 성립한다. 이는 $(x-1)(x-w)(x-w^2)\cdots (x-w^{n-1})=x^n-1$에 $x=-1$을 대입하면 얻을 수 있다. 따라서, $f(e^{\frac{2\pi }{K}t})$를 계산할 수 있게 되었다. $gcd(K,t)$의 값에 함숫값이 의존하므로 적당히 뫼비우스 함수를 곱해서 포함배제를 해주면 답을 구할 수 있다.

BOJ 32637 (물통)

clamp라고 알려진 함수를 합성하는 문제이다. ($y=max(a,min(b,x+c))$)

clamp의 합성은 clamp라는 사실이 잘 알려져 있다. 케이스워크를 통해 증명할 수도 있지만, clamp 함수에서 max, min, +의 합성 순서를 마음대로 바꿀 수 있다는 아이디어를 사용하면 max는 max끼리, min은 min끼리, +는 +끼리 합성하는 형태로 만들어줄 수 있다. (azber가 제시한 아이디어다.)

 

여담으로 IOI21 Distributing Candies의 하위호환이라 코드 복붙하면 풀린다.

BOJ 10407 (2 타워)

2로만 이루어진 power tower가 주어질 때 이를 3으로 나눈 나머지를 구하는 문제이다.

power tower의 높이가 2 이상이면 지수가 짝수라서 답이 1이 된다.

BOJ 19464 (King's roads)

$N$개의 정점이 있고 각 정점에는 $0$이상 $M$미만의 정수 $a_i$가 적혀있다. 간선 $\{i,j\}$의 비용이 $(a_i+a_j)$일 때, mst의 가중치를 구해야 한다.

적당히 쉬운 관찰을 통해 크루스칼이나 다른 mst 알고리즘을 최적화해서 풀 수 있다. 여기서는 mst가 어떻게 생겼는지 파악한 후 직접 계산하는 풀이를 설명한다.

 

일단 크기순으로 정렬해서 $a_1<a_2<\cdots <a_N$이라고 하자. ($i$번째 값에 $i\times {10}^{-9}$을 더하면 모든 가중치를 다르게 할 수 있다.) 어떤 해에서 $a_u+a_v<M$이고 $u,v>1$인 간선 $\{u,v\}$가 있다면, 이를 끊고 둘 중 하나를 $1$과 연결해주는 것이 이득이다. 따라서, $1$이 포함되지 않은 간선은 모두 $a_u+a_v-M$꼴의 코스트라는 것을 알 수 있다. 또한, $a_v+a_N<M$이라면 $v$는 $1$과 연결되어 있다.

 

$a_x+a_N\ge M$인 최소 $x$를 생각하자. $[x,N]$ 구간에서 어떤 두 점이 $1$과 연결되어있다면, 둘 중 하나를 자르고 두 정점을 직접 이어주는 게 더 이득이다. 즉, $[x,N]$ 구간에서 $1$과 연결된 정점은 유일하고, 이는 $x$여야 한다.

 

이제, $[x,N]$에 있는 정점들이 연결된 형태를 생각해 보자. 여기서는 코스트에 $-M$이 붙은 간선만 쓰인다. 어떤 두 간선 $\{u_1,v_1\}$, $\{u_2,v_2\}$가 포함관계가 아니라면 (예를 들어 $\{1,3\}$, $\{2,4\}$와 같은 형태) 추가 비용 없이 포함관계로 바꿀 수 있다. 따라서, 모든 간선이 포함관계인 최적해를 잡고 생각하자. $\{x,N\}$간선은 반드시 존재한다. 그다음 간선은 $\{x+1,N\}$ 또는 $\{x,N-1\}$인데, $a_x+a_{N-1}<M$이라면 반드시 $\{x+1,N\}$을 쓰게 된다. 그렇지 않다면, $\{x,N-1\}$을 쓰는 것이 최적이다. 이를 귀류법으로 증명한다.

 

$a_x+a_{N-1}\ge M$이면서 $\{x+1,N\}$을 쓰는 최적해가 있다고 가정하자. $x+1=N-1$인 경우는 이를 $\{x,N-1\}$로 바꾸는게 이득이므로 모순. $x+1<N-1$인 경우를 보자. $\{x+1,N-1\}$ 간선이 쓰인 경우, $\{x+1,N\}$을 지우고 $\{x,N-1\}$로 바꾸면 더 작은 해가 나온다. 그렇지 않은 경우, $\{x+2,N\}$이 쓰였다. $\{x+1,N\}$을 지우고 $\{x+1,N-1\}$을 쓰면 더 작은 해가 나온다. 따라서, 최적해라는 가정에 모순이다.

 

따라서, $\{x,N\}$에서 시작해서 재귀적으로 다음 간선을 결정해 나갈 수 있다. 이를 투포인터나 재귀로 구현하면 문제를 해결할 수 있다.

BOJ 19134 ($2x+2$)

집합 $\{1,2,\cdots ,n\}$의 부분집합 $S$가 임의의 $x\in S$에 대해 $(2x+2)\notin S$를 만족할 때 $|S|$의 최댓값을 구해야 한다.

모든 값에 2를 더하면 임의의 $x\in S$에 대해 $2x\notin S$를 만족하는 것으로 조건이 바뀐다. 어떤 홀수 $k$에 대해 $k,2k,4k,8k,\cdots$를 생각해 보면 $k,4k,16k,\cdots$를 포함하도록 선택하는 것이 최적이다. 홀수는 $n-n/2$개, $4k$꼴의 수는 $n/4-n/8$개,... 이므로 $n-n/2+n/4-n/8+\cdots$를 계산하면 된다. 처음에 2를 더하고 시작했기 때문에 $n$에 2를 더하고 식을 계산한 다음 1을 빼주면 된다. (1이랑 2는 전체집합에 없기 때문)

BOJ 18617 (From Modular to Rational)

소수 $m$을 질문하면 $\mathrm{mod}m$에서 $p{q}^{-1}$을 계산한 값을 알려준다. 이때, $p,q$를 찾아야 한다. $p,q$는 ${10}^9$ 이하의 양의 정수, $m$은 ${10}^9<m<{10}^{12}$인 소수다.

가능한 경우의 수가 대략 ${10}^{18}$이므로 적어도 질문 2번을 해야 한다. 한편, 질문 2번을 해서 $m=m_1{m}_2>{10}^{18}$인 경우의 답을 안다고 해보자. 어떤 $p^{\prime },q^{\prime }$이 존재하여 $p/q\ne p^{\prime }/q^{\prime }$이면서 $p{q}^{-1}\equiv p^{\prime }{q}^{\prime -1}(\mathrm{mod}m)$이려면 $|p{q}^{\prime }-p^{\prime }q|\ge m$이어야 한다. 그러나 이는 $p,q$가 ${10}^9$이하라는 조건에 모순이다. 따라서, 답이 유일하게 된다. 

 

이제 $y\equiv p{q}^{-1}(\mathrm{mod}m)$에서 $p$와 $q$를 구해보자. 식을 다시 쓰면 $p=mk+yq$이다. $1\le q\le {10}^9$ 범위에서 $mk+yq\ge 1$의 최솟값을 $p^{\prime }$이라고 해보자. $p$라는 해가 이미 있기 때문에 $p^{\prime }\le {10}^9$이고, $(p^{\prime },q)$는 유효한 해이므로 $p^{\prime }$이 우리가 찾고 싶어 하던 $p$와 동일하다는 것을 알 수 있다. 따라서, 주어진 $x$범위에서 $ax+by\ge 1$의 최솟값을 구하는 문제로 바꿀 수 있다. 이는 유클리드 호제법으로 풀 수 있다. $x$ 대신 $y$를 기준으로 바꾸면서 계수를 작게 줄이면 동일한 형태의 더 작은 문제가 나온다. 좌표평면에 직접 점을 찍고 점이 어디로 이동하는지 시각화하면 이해하기 쉽다.

 

추가로, crypto에서 Lattice reduction이라는 이름으로 알려져 있다고 한다. 나중에 기회가 되면 공부할 생각이다.

BOJ 13949 (쉬운 문제)

$a^2+b^2+c^2=k(ab+bc+ca)+1$의 정수해 $(a,b,c)$를 1000개 구하는 문제이다.

$a$에 대해 생각하면 주어진 식은 $a$에 대한 이차식이므로 $(a,b,c)$가 해일 때 $(k(b+c)-a,b,c)$도 해가 된다. (vieta jumping) $b,c$에 대해서도 마찬가지이므로 초기해 $(1,0,0)$에서 시작해서 해를 계속 만들어나가면 된다. 출력 조건을 만족하는 해가 1000개 이상 만들어지는 이유는 잘 모르겠다.

BOJ 18574 (Fractional XOR Maximization)

닫힌 구간 2개가 주어질 때 각 구간에서 실수를 1개씩 뽑아 xor을 최대화하는 문제이다.

일단 $2^{-60}$을 곱하면 모든 구간의 끝점을 0 이상 1 이하로 만들 수 있다. 이제 소수점 첫째 자리에 해당하는 비트를 결정하고 재귀적으로 문제를 해결하면 된다. 구간의 길이가 0인 경우, 두 구간이 1/2를 동시에 포함하는 경우 등 예외처리해야 하는 케이스가 조금 있다. 답의 분모가 매우 클 수 있기 때문에 파이썬을 쓰는 것이 편하다.

BOJ 19118 (Master Zhu and Polygons)

정$N$각형에서 점 $M$개를 선택해서 만든 다각형에 예각이 $K$개 있는 경우의 수를 묻는 문제이다. ($N$은 홀수)

예각의 개수는 최대 3개이며, 사각형 이상이면 최대 2개이다. 이는 외접원에서 예각이 호의 과반을 차지하기 때문이다. 가능한 모든 다각형을 만들었을 때 예각의 개수, 예각이 2개인 다각형 개수를 계산하면 포함배제로 답을 구할 수 있다. 예각이 2개인 다각형은 예각이 한 변을 공유하기 때문에 이 변을 고정하고 세면 식을 얻을 수 있다. 하키스틱과 같은 항등식으로 식을 잘 정리하면 $O(1)$에 계산할 수 있는 형태로 바꿀 수 있다. 난 귀찮아서 gpt한테 시켜서 답을 구했다.

BOJ 19087 (Faint)

$\{1,2,\cdots ,n\}$의 크기 $k$ 부분집합을 사전순으로 $(\genfrac{}{}{0ex}{}{n}{k})\times k$ 표에 나열한다. 이를 $A$라고 할 때 $\sum _{i=1}^{(\genfrac{}{}{0ex}{}{n}{k})-1}|A_{i,m}-A_{i+1,m}|$을 구하는 문제이다.

$A_{i,m}$이 변하는 형태를 생각해 보면 천천히 증가하다가 최댓값 $n-k+m$을 찍고 떨어진 다음 다시 천천히 증가하는 형태이다. 떨어지는 순간은 $m-1$짜리 prefix가 변하는 순간과 동일하다. 따라서, 떨어지고 난 직후의 값을 $i$라고 할 때, $2(n-k+m-i)(\genfrac{}{}{0ex}{}{i-2}{m-2})$를 답에 더해주면 된다. 맨 처음에는 떨어지지 않고 그냥 시작하기 때문에 이 값을 따로 빼주면 된다.

BOJ 28009 (LaLa and Monster Hunting (Part 2))

삼각형에 길이 3 path가 붙은 형태의 그래프가 몇 개 나타나는지 세는 문제이다.

삼각형의 개수부터 세보자. 정점을 차수 순으로 정렬했을 때 정점 $i$가 $or{d}_i$번째에 온다고 하자. $or{d}_u<or{d}_v$일 때 간선 $\{u,v\}$의 방향을 $u\to v$로 결정하면 정점의 outdegree는 $\sqrt{2M}$이하라는 것을 알 수 있다. (잘 생각해 보자.) 따라서, 이 그래프에서 길이 2의 path $(u,v,w)$를 순회하면 $O(M\sqrt{M})$에 삼각형의 개수를 셀 수 있다. 비슷한 방식으로, 차수가 가장 큰 정점과 마주 보는 정점을 고정하고 길이 2의 path 개수를 세면 사각형의 개수도 셀 수 있다.

 

문제에서 제시한 그래프는 어떤 간선이 있고, 한쪽에는 삼각형, 다른 쪽에는 길이 2의 path가 붙은 형태이다. 정점 중복을 고려하지 않고 일단 센 후, 정점이 겹치는 경우를 빼주면 된다. 정점이 2개 겹치는 경우는 변을 공유하는 삼각형 형태가 유일하다. 정점이 1개 겹치는 경우는 변을 공유하는 삼각형에 간선 1개가 추가로 달린 형태, 변을 공유하는 삼각형과 사각형, 점을 공유하는 삼각형 형태가 있다. 삼각형과 사각형 세는 알고리즘을 응용하면 모두 셀 수 있다.