#USACO 2016 December Contest

Bronze

Square Pasture

잘 정사각형으로 덮어주면 된다.

source

Block Game

각 카드에 대해 앞면과 뒷면에 대해 각 알파벳이 몇번 나왔는지 세주고,

각 알파벳에 대해 최대값을 더해주면 꼭 준비해주어야 할 블럭의 수를 알 수 있다.

source

The Cow-Signal

다중 반복문 연습하면 된다.

못 풀면 별찍기부터 다시 공부해야 한다.

source

Silver

Counting Haybales

각 건초더미들의 위치를 넘버링해서 set에 넣어준 후

각 구간에 대해 s, e+1의 lowerbound를 구해준 후 처리해주면 된다.

source

Cities and States

앞에 두 글자에 대해 카운팅 해주면서 풀어주면 된다.

문제에서 앞 두글자와 뒤 두글자가 같은 경우엔 카운팅 하지 않는다.

source

Moocast

각 소에 대해 dfs를 돌려보면 된다.

source

Gold

Moocast

x가 가능하면 x+1도 가능하다는 성질을 이용해서 파라메트릭 서치를 돌리면 된다.

결정된 x에 대해 bfs나 dfs를 돌려서 모든 그래프가 이어져 있는지 체크하면 된다.

source

Cow Checklist

D(i)(j)(0) = a[1]~ a[i] / b[1]~b[j]까지 탐색했 고 a[i]위치에 있는 상태까지 최소비용

D(i)(j)(1) = a[1]~ a[i] / b[1]~b[j]까지 탐색했 고 b[i]위치에 있는 상태까지 최소비용

초기값을 주의해서 넣어주어야 한다.

source

Lasers and Mirrors

상하좌우에 대해 간선을 준 후 다익스트라나 큐를 2개를 이용한 bfs를 통해 구현해주면 된다.

source

Platinum

Lots of Triangles

가장 아래 점 P를 잡고 num(a)(b)를 삼각형 (P,a,b)에 속한 점의 개수 라 정의하자

삼각형(a, b, c)에 속한 점의 개수는 삼각형(P, a, b), 삼각형(P, a, c), 삼각형(P, b, c)으로 표현 가능하다

각도를 정렬하면 깔끔하게 케이스를 나누어서 풀 수 있다.

아래 코드는 각도정렬을 하지 않았다.

source

Team Building

D(i)(j)(k) = A[1]~A[i], B[1]~B[j]까지 존재할 때 무조건 이기게 k마리를 뽑는 경우의 수

포함배제로 기본 식을 준 후 조건에 맞으면 가져오는 식으로 점화식을 구성하자.

D(i)(j)(k) = D(i-1)(j)(k) + D(i)(j-1)(k) - D(i-1)(j-1)(k) + (a[i]>a[j]?D(i-1)(j-1)(k-1):0)

이문제는 mod가 앞의 다른 유사코문제와 다르게 1e9+9이다.

source

Robotic Cow Herd