#USACO 2016 February Contest

Bronze

Milk Pails (Bronze)

X를 몇 번 쓸지 Y를 몇 번 쓸지 전부다 결정해 준 후 최소 차이를 출력해주면 된다.

source

Circular Barn (Bronze)

모든 위치에 구멍을 뚫어보는 식으로 해본 후 시뮬레이션을 돌리고 최소값을 출력해주면 된다.

source

Load Balancing (Bronze)

모든 (x, y)좌표에 대해 (x+1,y+1)에 교차점을 두고 각 사분면에 점이 몇개 있는지 세준 후에 최대값을 구해주면 된다. O(n^3)

source

Silver

Circular Barn (Silver)

최대 길이 n번 기다리고 n번 이동할 것이기 때문에 2n시간동안 시뮬레이션을 돌려주면 된다.

source

Load Balancing (Silver)

N^3에서 상수를 잘 조절하면 풀 수 있다.

좌표압축 후 누적합을 구해서 n^2에 풀어도 무방하다.

source

Milk Pails (Silver)

가능한 모든 상태를 BFS를 통해 얻어주면 해결할 수 있다.

source

Gold

Circular Barn (Gold)

각 숫자를 최대한 반시계방향에 있는 0에 준다는 생각으로 문제를 해결할 수 있다.

시작점으로 적당한 점을 잡아서 시뮬레이션해주면 문제를 해결할 수 있다.

source

Circular Barn Revisited

원순열은 그 순열을 두번 쓰면 깔끔하게 표현 가능하다.

C(j)(k) = j에 구멍을 뚫었고 j~k까지 있을 때 최소비용

D(i)(s)(e) = i개의 구멍을 뚫었고 s~e까지 있을 때 최소비용 으로 정의하면

D(i)(s)(e) = min(C(s)(p) + D(i-1)(p+1)(e))가 된다.

k, e-s+1이 n인 구간에 대해 답을 구해주면 된다.

source

Fenced In (Gold)

NM개의 간선을 남기면 문제를 해결할 수 있다.(MST느낌)

가중치가 큰 선분들부터 사이클이 생기는지 체크하면서 가처리해주자

source

Platinum

Load Balancing (Platinum)

각 사분면에 위치에 최대 x개의 점을 둘 수 있다고 한다면 최대 x+1개의 점도 둘 수 있을 것이다.

결정을 하면 왼쪽 위에 대해서 가능한 y좌표는 단조 증가할것이고, 오른쪽 위에대해서 가능한 y좌표는 단조 감소할것이고

왼쪽 아래에 대한 y좌표는 단조 감소할 것이고 오른쪽 아래에 대한 y좌표는 단조 증가할 것이다.

위에 대해서는 min연산을, 아래에대해서는 max연산을 한 뒤에 각 위치에 대해 겹치는 부분이 있는지 체크하면 임의의 해 x에 대해 가능한지 체크할 수 있다.

총 시간복잡도 O(nlog^2n)

Fenced In (Platinum)

NM개의 간선을 남기면 문제를 해결할 수 있다.(MST느낌)

가중치가 큰 선분들부터 사이클이 생기는지 체크하면서 가처리해주자

근데 제한이 크니 같은 처리가 되는 선분의 길이에 대해서는 묶어서 처리해주자.

source

Circular Barn (Platinum)

원순열은 그 순열을 두번 쓰면 깔끔하게 표현 가능하다.

C(j)(k) = j에 구멍을 뚫었고 j~k까지 있을 때 최소비용

D(i)(s)(e) = i개의 구멍을 뚫었고 s~e까지 있을 때 최소비용 으로 정의하면

D(i)(s)(e) = min(C(s)(p) + D(i-1)(p+1)(e))(s<=p<=e-1)가 된다.

여기서 하나를 더 관찰하면 s, e-1까지 있을 때 잡는 피봇 p보다 s, e까지 있을 때 잡는 피봇 p가 크거나 같을 것이고

s+1, e까지 있을때 잡는 p보다 s, e까지 있을 때 잡는 피봇 p가 작거나 같을 것이다.

P(i)(s)(e) = D(i)(s)(e)가 잡은 피봇 으로 정의한다면

D(i)(s)(e) = min(C(s)(p) + D(i-1)(p+1)(e)) (P(i)(s)(e-1) <= p <= P(i)(s+1)(e))

그럼 이제 D배열을 kN^2만에 채워줄 수 있다.

k, e-s+1이 n인 구간에 대해 답을 구해주면 된다.

source