전체 글 (21) 썸네일형 리스트형 2026년 2월 6일 JAG Summer Camp 2019 Day 1AiGo-Non-Trivial Common Divisor-Universal and Existential Quantifiers$l$을 기준으로 정렬하여 구간이 겹치면서 가장 오른쪽에 있는 $r$을 찾는다.구간 $[0, L)$을 커버하지 못한다면 적어도 하나의 $x$ 좌표가 비어있다. 모든 $x$에 대해 $x$를 덮지 않도록 구간을 최대한 추가해본다.Permutation Sort$P$의 모든 원소에 대해 목표까지의 거리와 사이클의 길이를 계산한다. 답은 중국인의 나머지 정리로 구할 수 있다.Consistent TradingPotential graph에 모순이 존재하는지 판별하는 문제이다. 퍼텐셜 차이가 곱셉으로 정의되어 퍼텐셜이 매우 커질 수 있다. 따라서 $2.. 2026년 2월 5일 AtCoder Regular Contest 203 (Div. 2)A - All Winners각 팀에서 대표를 둘씩 뽑아서 매칭하면 모든 게임에 승리하는 사람을 $N$명 만들 수 있다. 각 그룹에 한 명씩 있는 경우 모든 게임에 승리하는 사람은 최대 한 명이다. 정답은 $\lfloor\frac{M}{2}\rfloor\times N + (M \bmod 2)$이다.B - Swap If Equal Sum$A = B$인 경우는 자명하다. $1$의 개수가 같고 popcount가 2 이상이면 항상 가능하다. popcount가 1인 경우 $100$, $001$과 같은 케이스를 고려하여 판단한다.C - Destruction of Walls$H\times W$ 격자 그래프에서 $K$개의 간선을 선택할 때 $(1,1)$과 .. 2026년 2월 4일 최소 버텍스 커버Kőnig's theorem In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.이분 그래프에 대해 최대 매칭 = 최소 버텍스 커버 = 최대 유량 = 최소 컷 이다.이분 그래프에서 최소 버텍스 커버를 $C$라고 할 때 최대 독립 집합 $S$는 $V\setminus C$이다.이분 그래프 네트워크에서 min cut을 구하고 cut edge와 연결된 정점을 색칠하면 이는 최소 버텍스 커버이다.4에 대한 간단한 증명. source 또는 sink와 연결된 간선의 용량은 $1$이고 나머지 간선의 용량은 $\infty$ 이므로 cut e.. 2026년 2월 3일 JAG Summer Camp 2023 Day 3Odd trip plans동적 그래프 $G$에서 정점 $u$에서 시작해서 정점 $v$에서 끝나는 walk 중에 $1,2,\cdots,N$의 모든 정점을 홀수번 방문하는 walk가 존재하는지 판별하는 문제이다. $G$는 연결 요소라고 가정한다. Walk $W$에서 정점 $u$의 빈도를 $f_u$, $W$의 길이를 $L$이라고 할 때, $f_u \equiv 1 \pmod 2, \forall u \in G$와 $L \equiv N - 1 \pmod 2$는 필요충분조건이다.$f_u \equiv 1 \pmod 2, \forall u \in G \implies L \equiv N - 1 \pmod 2$$\sum_{i=1}^N {f_i} \equiv \sum_{i=1}^.. 2026년 2월 2일 JAG Summer Camp 2023 Day 3Roller Coaster-Break a PrisonBFS.Camp room assignment주어진 $m$에 대해 정답 수열을 $A_n$($1 \le n \le m$)이라고 하자. $S_n = \sum_{i=0}^{n-1}{\binom{2n}{i}(m-1)^i}$에 대해 $A_n = m^{2n} - mS_n$이다. 이는 $O(m^2)$에 계산 가능하고 이를 최적화하는 방법은 3가지 정도가 존재한다.방법 1. $\binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}=\binom{n-2}{k}+2\binom{n-2}{k-1}+\binom{n-2}{k-2}$라는 사실을 이용하면 점화식 $S_{n+1}=m^2S_n+(m-1)^n\bin.. 2026년 1월 31일-2월 1일 AtCoder Beginner Contest 443-AtCoder Regular Contest 207 (Div.1)A - Affinity for Artifacts주어진 수열 $a$에 대해 $\sum_{i=0}^{N-1}{\max(0, a_{p_i} - i)}$를 만족하는 순열 $p_i$의 개수를 구하는 문제이다. 색이 다른 $N$개의 공이 있고 $i$번째 공에는 수 $a_i$가 적혀있다. 조건을 만족하도록 공을 $1 \times N$ 격자에 채워넣는 문제로 바꾸어서 생각하자. 왼쪽부터 오른쪽으로 격자칸을 순회하면서 공을 채워넣는다. 이때 격자칸을 건너뛸 수도 있다. $i$번째 격자에 방문했을 때는 $i$가 적혀있는 공을 왼쪽의 빈 칸에 넣을지, $i$에 놓을지, 아니면 미래에 오른쪽 칸에서 처리할지 결정.. 2026년 1월 30일 Codeforces Round 1077 (Div. 2)A-C는 생략한다.D. Shortest Statement Ever구성적 해 또는 그리디 풀이가 존재할 것이라고 예상했지만 생각이 나지 않아서 $31 \times 2 \times 2$ 자릿수 DP를 4번 푸는 것으로 해결했다.정해는 다음과 같다.$x \& y = 0$일 때는 $p = x, q = y$로 놓을 수 있다. $x \& y \neq 0$일 때는 $i = \log_2{(x \& y)}$에 대해 $(p, q)$의 순서쌍 $(\lfloor \frac{x}{2^i} \rfloor \times 2^i + 2^i, y)$, $(\lfloor \frac{x}{2^i} \rfloor \times 2^i - 1, \lfloor \frac{y}{2^i} \rfl.. 2026년 1월 29일 Tree Isomorphism ITree isomorphism을 판별하기 위해 다음과 같은 해시 함수 $h(u)$를 사용할 수 있다. 루트가 있는 트리 $T$의 정점 $u$, $u$의 자식 정점 $v$, 해시 함수 $f$, 임의의 상수 $s$에 대해 $u$를 루트로 하는 서브트리의 해시를 $h(u) = f \left (s + \sum h(v) \right )$로 정의한다.Tree Isomorphism II루트가 없는 트리에 대해 tree isomorphism을 판별할 때에는 트리의 center 또는 centroid를 루트 노드로 설정한다. center 또는 centroid가 두 개 있다면 두 해시의 최솟값 또는 최댓값을 사용한다.평행우주Tree isomorphism 기본 문제.Tree Automorphi.. 이전 1 2 3 다음