#USACO 2017 January Contest

Bronze

Don't Be Last!

두번째로 생산량이 많은 소를 구해주면 된다.

source

Hoof, Paper, Scissors (Bronze)

가능한 모든 조합을 결정해준 후 최대값을 출력해주면 된다. (3! = 6가지)

이를 재귀를 이용하거나 for문을 중첩한 코드로 구현하면 코드가 복잡해지니 경우가 적은 점을 이용해서 배열에 미리 넣어준 후 처리해주자.

source

Cow Tipping

오른쪽 아래부터 1이면 뒤집는식으로 처리해주면 된다.

두번 연산하면 원상태로 되돌아오기 때문에 1번 연산하거나 0번 연산하는것이 최선이다.

source

Silver

Cow Dance Show

k가 가능하다면 k+1도 가능하다는 점을 이용해서

파라메트릭서치를 이용해 극점을 찾아주면 된다.

결정된 문제를 해결할 때 최소 힙을 활용하면 쉽게 해결할 수 있다.

source

Hoof, Paper, Scissors (Silver)

딱 한번만 바꿀 수 있기 때문에 각 가위,바위,보에 대해 앞에서부터 이기는 횟수, 뒤에서부터 이기는 횟수를 저장해주자.

max(정방향i + 역방향i+1)가 정답이다.

dp로 풀어도 무방하다.

source

Secret Cow Code

F(n, x)를 다음과 같이 정의하자

F(n, x) = 길이 n짜리 문자열에서 x번째 문자

문자열을 만드는 정의에 따라

x가 n/2이하에 위치해 있다면 F(n/2, x)가 문자가 될 것이고

그 이후에 있다면 F(n/2, (x - 1)%(n/2))가 문자가 될 것이다.

source

Gold

Balanced Photo

각 소에대해 좌표압축을 해준 후 sum인덱스트리를 이용해 L[i], R[i]를 구해주자.

그 후 차이가 2배이상 나는 소를 카운트해주면 정답을 구할 수 있다.

source

Hoof, Paper, Scissors (Gold)

Dijk = 1~i까지 j번 바꾸었고 k를 내고 있을 때 최대 승리 횟수

라 정의한 후 점화식을 세워서 문제를 해결하면 된다.

source

Cow Navigation

x1,y1,방향1,x2,y2,방향2에 대해 중복체크를 해주면서 BFS를 돌려주면 된다.(O(n^4 x 4 x 4))

source