2026년 2월 6일

JAG Summer Camp 2019 Day 1

AiGo

-

Non-Trivial Common Divisor

-

Universal and Existential Quantifiers

1. $l$을 기준으로 정렬하여 구간이 겹치면서 가장 오른쪽에 있는 $r$을 찾는다.
2. 구간 $[0, L)$을 커버하지 못한다면 적어도 하나의 $x$ 좌표가 비어있다. 모든 $x$에 대해 $x$를 덮지 않도록 구간을 최대한 추가해본다.

Permutation Sort

$P$의 모든 원소에 대해 목표까지의 거리와 사이클의 길이를 계산한다. 답은 중국인의 나머지 정리로 구할 수 있다.

Consistent Trading

Potential graph에 모순이 존재하는지 판별하는 문제이다. 퍼텐셜 차이가 곱셉으로 정의되어 퍼텐셜이 매우 커질 수 있다. 따라서 $2^{61}-1$정도의 큰 소수를 잡아서 해싱한다.

Route Calculator Returns

연산자의 우선 순위가 존재하므로 곱셈 항을 단위로 하여 생각한다. 합, 곱셈 항의 중간 상태, 곱셈 항의 초기 상태, 경로의 수를 관리하면 DP로 풀 수 있다.

Rooks Game

룩들이 서로 공격할 수 없는 상태를 만들어야 한다.
룩이 가장 많이 남아있는 상태는 행과 열에 대한 이분 그래프를 만들어서 최대 유량을 구하는 것으로 찾을 수 있다.
룩이 가장 적게 남아있는 상태는 컴포넌트 당 하나의 룩만 남아있는 경우이다. 서로 다른 컴포넌트의 룩은 서로 공격할 수 없고, 한 컴포넌트의 룩은 스패닝 트리의 리프부터 움직이면 하나의 룩만 남길 수 있다.