PS 이야기

문제 및 채점: oj.uz 서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향으로 연속하게 $K$ 개의 식물 중에서 $i$ 번 식물보다 키가 큰 식물의 수를 $R[i]$에 기록했다. 배열 $R$이 주어지고, 식물 번호 $i$와 $j$ 쌍들이 주어졌을 때, 배열 $R$의 내용으로 $i$번 식물과 $j$번 식물의 크기를 비교할 수 있는지, 비교 가능하다면 어떤 식물의 크기가 큰지 확인하는 문제다. 이 문제에서 각 쿼리는 실시간(online)으로 해결해야 된다. 풀이를 $N = 7$, $K = 3$, $R = [0, 1, 1, 2, 0, 0, 1]$인 경우를 예시..

문제 및 채점: oj.uz 티켓은 $N$ 개의 색 중 한 가지 색을 띄며, 각 색마다 $M$ 개의 티켓이 있다. 티켓에는 수가 적혀있는데, 티켓에 적힌 수는 서로 다를 수 있다. $K$ 번의 라운드를 진행할거고 각 라운드마다 $N$ 개의 서로 다른 색의 티켓을 뽑고, 어떤 수 $b$를 임의로 정해 $b$와 $N$ 개의 티켓에 적힌 수와 차이값을 구해 모두 더한 값을 $S$라 하자. 이때, $S$의 값이 최소가 되도록 수 $b$를 정한다. 한 라운드에 쓰인 티켓은 소멸되기 때문에 한 티켓은 최대 한 라운드에서만 사용 가능하다. 각 라운드마다 티켓을 적절히 골라 모든 라운드의 $S$ 값들을 다 더한 값을 최대화하는 문제다. 편의상 $N$은 짝수다. 우선, 각 라운드에서 $S$ 값을 계산할 때 문제에서 정의한..

문제 및 채점: oj.uz 정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq 3$이다. $p$ 배열의 내용만 주어졌을 때, 원래 그래프를 복원하는 것이 가능한지 확인하고, 가능하다면 그래프를 복원하는 문제다. 서브태스크 1 (11 점) $p[i][j] = 1$이다. 트리에서 각 정점 사이에 경로는 항상 한 개만 존재한다는 사실을 생각해보자. 즉, 모든 트리에 대해 $p[i][j] = 1$이기 때문에, 아무 트리로 그래프를 복원하면 된다. 아래는 만들 수 있는 단순한 트리 중 하나다. 서브태스크 2 (10 점) $p[i][j] = 0\ \mathrm{or}\..