-
Number Theory Techniques
https://www.acmicpc.net/category/detail/4072 해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다. F. Queens’ Rye Cafe 요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다. Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다. Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와...
-
양자컴퓨팅으로 PS하는법
제목을 조금 자극적이게 “양자컴퓨팅으로 PS하는 법”이라고 설명했지만, 아직 일반적인 PS를 하는 데 양자컴퓨터를 사용하는것은 어렵다. 그래도 그나마 PS스러운 max cut 문제를 양자컴퓨터로 해결하는 방법을 최대한 쉽게 소개하고자 한다. 나중에도 양자컴퓨터를 사용한 소개할만한 알고리즘이 있다면 소개해볼 계획이다. Max cut 문제란? Max cut 문제는 주어진 그래프를 두 집합으로 잘 분리하여 두 집합 사이를 연결하는 간선의 수를 최대화하는 문제이다. 그림 1. Maxcut 예시.흰색과 검은색 정점 집합으로 위와 같이 분리하면 둘 사이를 연결하는 간선(빨간색)이 5개로 최대가 된다. 따라서 이...
-
Folding Part 2: HyperNova
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Verifiable Computation은 Generator $\mathcal{G}(1^\lambda) \rightarrow pp$: security parameter $\lambda$를 받고 public parameter $pp$를 만든다 Encoder $\mathcal{K}(pp, F) \rightarrow (pk, vk)$: public parameter $pp$와 반복할 함수 $F$를 받고, prover key 및 verifier key $pk, vk$를 만든다 Prover $\mathcal{P}(pk, (i, z_0, z_i), \omega_i, \Pi_i) \rightarrow \Pi_{i+1}$은 결과 $z_i$와 이에 대한 IVC proof $\Pi_i$를 받고, $z_{i+1} =...
-
문자열 해싱
이번 글에선 해싱의 다양한 활용을 정리하고자 한다. 너무 기본적인 내용이나 필자도 모르는 너무 고급 기술은 다루지 않고, solved.ac 기준 다이아 중하위 수준까지의 문제를 해싱을 이용해 풀어보려는 사람들에게 적합하다. 해시값을 관리하는 몇가지 방법들을 소개하고, 마지막으로는 며칠 전에 출제된 따끈따끈한 문제인 ICPC 2023 Seoul Regional에 출제된 E번 문항을 해싱을 써서 해결하는 방법을 소개하며 글을 마무리한다. 해싱이란? 문자열 x[0] ~ x[l-1] 이 주어져있을 때, 소수 $p, M$을 사용하여 계산한 해시값 $(\sum_{i=0}^{l-1} x_ip^i) \text{ mod M}$ 을 비교하여 다른...
-
Taylor Shift, Sampling Points Shift
개요 최근에 Polynomial Shift를 사용하는 문제를 여러 대회에서 보았기 때문에 이 글을 작성하게 되었습니다. 다항식 $f(x)$와 정수 $c$가 주어졌을 때 새로운 다항식 $f(x+c)$를 구하는 것을 Taylor Shift라고 부릅니다. $N$차 미만의 다항식 $f(x)$가 숨겨져 있고 값 $f(0), f(1), \cdots, f(N-1)$과 정수 $c,M$이 주어졌을 때 $f(c), f(c+1), \cdots, f(c+M-1)$을 구하는 것을 Sampling Points Shift라고 부릅니다. 위의 두 문제는 조합론 문제를 해결할 때 종종 유용한 도구가 되어 줍니다. 두 문제 모두 단순하게 풀면 너무 느리지만, FFT를 사용한다면 효율적으로...