#USACO 2017 December Contest

Bronze

Blocked Billboard

사각형의 정의역이 작다는 점에 주목해서 맵을 만들어서 해결

source

The Bovine Shuffle

The Bovine Shuffle

각 문자열들을 입력받은 후 a[a[a[i]]]번째 문자열이 정답

source

Milk Measurement

Milk Measurement

각 문자열을 잘 넘버링 해준 후(string, map을 이용하면 편리함) 각 쿼리를 시간순서로 정렬

같은 시간을 가지는 노트가 없기 때문에 최대값과 최대값의 개수를 이용해서 케이스를 나누어 해결하면 되는데

저 부분을 못읽어서 n이 작다는 점을 이용해 최대값 리스트를 뽑아내는 식으로 해결

source

Silver

My Cow Ate My Homework

My Cow Ate My Homework 무조건 앞에서 부터 소가 먹기 때문에 뒤에서 부터 처리해주면 쉽게 처리할 수 있다.

최소값과 합연산은 결합법칙이 성립하기 때문에 뒤에서부터 누적 최소값 배열과 누적 합배열을 이용해서 처리

값이 변할 일 없기 때문에(정적이기 때문에) 인덱스트리와 같은 logn타임의 자료구조를 이용할 필요가 없다.

source

Milk Measurement

Milk Measurement

각 문자열을 잘 넘버링 해준 후(string, map을 이용하면 편리함) 각 쿼리를 시간순서로 정렬.

같은 시간을 가지는 노트가 없기 때문에 최대값과 최대값의 개수를 이용해서 케이스를 나누어 해결.

N제한이 크기 때문에 인덱스트리를 활용해 문제를 풀어주면 된다.

source

The Bovine Shuffle

The Bovine Shuffle

각 숫자들을 정점으로 본 후 각 a[i]에 대해 i번 정점에서 a[i]정점으로 가는 간선을 준 후 사이클에 포함된 정점의 개수를 세주면 된다.

source

Gold

A Pie for a Pie

A Pie for a Pie

무조건 상대방에게 가치 0짜리 파이를 줘야 행복하게 엔딩이 나기 때문에 가치0짜리에서 거꾸로 스탭수를 세주는 식으로 문제를 풀어주면 된다.

간선가중치가 1이기 때문에 bfs가 가장 빠른 최단경로 알고리즘이다.

source

Barn Painting

Barn Painting

임의의 정점을 트리의 루트로 잡은 후

Di,j = i를 루트로 하는 서브트리가 있고 i정점을 j색상으로 칠했을 때 경우의 수

Di,j = MUL(sum(Di,j랑 다른색))

ans = sum(D루트,색상)

source

Haybale Feast

Haybale Feast

투포인터 + 인덱스트리

source