#USACO 2017 February Contest

Bronze

소가 길을 건너간 이유 1

각 소들에 대해 마지막으로 입력된 위치를 저장하는 배열을 하나 만들어서

입력이 될 때마다 마지막으로 입력된 위치와 다르다면 정답을 카운트해주면 된다.

source

소가 길을 건너간 이유 2

각 알파벳에 대해 등장 위치를 [xi, yi]라 하자

두 알파벳 i, j가 겹치는 경우에는 xi < xj < yi < yj 혹은 xj < xi < yj < yi를 만족할 것 이다.

각 yi에 대해 아직 닫히지 않은 구간의 개수를 구해주면 된다.

source

소가 길을 건너간 이유 3

시뮬레이션 해주면 된다.

source

Silver

소가 길을 건너간 이유 4

그리디하게 문제를 풀어주면 된다.

닭에대해 소를 배정하는식으로 문제를 해결해 주면 된다.

각 닭에 대해 배정할 수 있는 소들 중 끝점이 가장 작은 소를 배정해주면 된다.

min힙을 이용하면 쉽게 해결할 수 있다.

소에대해 닭을 배정하는식으로 문제를 풀려고 하면 문제를 해결하기 어렵다.

정렬기준을 s로 잡아야할지 e로 잡아야할지 애매하기 때문이다.

source

소가 길을 건너간 이유 5

고장난 신호등에 대해 체크를 해준 후,

체크배열에 대한 누적합을 만들면서 구간 k의 최소합을 구해주면 된다.

source

소가 길을 건너간 이유 6

각 위치(x, y)를 집합으로 본 후 상하좌우에 길이 없는 위치들과 union해준다.

k x (k-1) - sum((각 집합에 원소의 개수) x (각 집합의 원소의 개수 - 1))가 정답이 된다.

source

Gold

소가 길을 건너간 이유 7

3칸뛰어서 갈 수 있는 위치에 t x 3 가중치의 간선을 준 후 다익스트라를 통해 시작지점으로부터 최단거리를 다 구해준다.

(n-1, n-1)으로 0칸, 1칸, 2칸을 뛰어서 올 수 있는 거리중 최소값이 정답이다.

source

소가 길을 건너간 이유 8

LCS문제를 풀 듯 문제를 해결할 수 있다.

D(i)(j) = 왼쪽에 소가 i까지 오른쪽에 소가 j까지 있을 때 최대 개수라 정의하면

D(i)(j)는 기본적으로 D(i)(j-1), D(i-1)(j)에 해당하는 해를 포함할 것이다.

i와 j와 매칭을 시켰을 때 D(i)(j) = D(i-1)(j-1) + 1

i와 j와 매칭을 시킬 수 없을 때 D(i)(j) = max(D(i)(j-1),D(i-1)(j))

ans = D(n)(n)

source

소가 길을 건너간 이유 9

브론즈 2번 풀이를 인덱스트리를 이용해 구현해주면 된다.

source

Platinum

소가 길을 건너간 이유 10

일단 각 왼쪽 소가 오른쪽 소에 몇번째와 매칭되는지 저장해주자.

A[i] = 왼쪽 i번째 소가 매칭되는 오른쪽 소의 번호

겹치는 선분의 개수는 A배열의 inversion의 개수가 된다 (i < j , A[i] > A[j]인 (i, j)쌍의 개수)

그럼 각 왼쪽 소가 길을 건널 때 변화하는 inversion의 개수를 관찰해보면

자신보다 작은 숫자를 가지는 소들의 수 만큼 inversion이 감소할거고 (A[i]-1)

자신보다 큰 숫자를 가지는 소들의 수 만큼 inversion이 증가할것이다. (n- A[i])

O(n)만에 각 소들이 건널 때 생기는 inversion의 변화를 구할 수 있다.

오른쪽 소에 대해서도 똑같은 처리를 해준 후 최소값을 출력해주면 된다.

source

소가 길을 건너간 이유 11

각 왼쪽 소들이 최대 9마리의 오른쪽 소에 매칭된다는 성질을 이용해서

인덱스트리를 이용한 LIS를 구해주면 된다.

단, 같은 왼쪽 소에 대해 처리할 때 인덱스가 큰 오른쪽 소부터 LIS를 구해주어야 한다.

source

소가 길을 건너간 이유 12

머지소트과정에서 inversion을 구하는 식으로 처리하고, 인덱스트리를 이용해 처리하면 O(nlog^2n)에 문제를 해결할 수 있다.

source