#USACO 2017 US Open Contest

Bronze

The Lost Cow

y를 만날 때 까지 시뮬레이션을 해주면 된다.

범위가 작기 때문에 한 스텝씩 시뮬레이션 해도 충분히 시간내에 나온다.

코드

Bovine Genomics (Bronze)

각 위치별로 점박이소의 A,C,G,T의 구성 / 일반소의 A,C,G,T의 구성을 구해준 후 겹치는 인덱스가 있는지 판단해주면 된다.

비트연산을 이용하면 쉽게 코드를 구현할 수 있다.

코드

Modern Art (Bronze)

각 색상별로 커버되는 최소 직사각형을 구해서 그 직사각형 내에 있는 색상들에 대해 답이 될 수 없다고 처리해준다.

마지막에 답이될 수 있는 색상들에 개수를 카운트 해준 후 출력하면 해결된다.

코드

Silver

Paired Up

제일 값이 큰 소와 제일 값이 작은 소를 계속 매칭시켜주면 그게 최적이다.

소들을 우유 생산량순으로 정렬한 후에 처리해주자.

M범위가 크기 때문에 포인터를 두개를 잡아서(투포인터) 입력에 대해서 일괄적으로 처리해줄 수 있다(O(n)

코드

Bovine Genomics (Silver)

M제한이 작다는 점을 이용해서 문제를 해결할 수 있다.

각 자리 i, j, k를 결정해 준 후 체크배열을 만들어서 같은 부분이 있는지를 처리해주면 O(NM^3)에 문제를 해결할 수 있다.

비트연산을 이용하면 쉽게 처리할 수 있다.

코드

Where's Bessie?

각 직사각형을 결정한 후 그 직사각형이 해당하는 조건에 맞는지 처리를 해주면 된다.

여기서 생각해야 할 점은 임의의 하나의 답에 대해 부분집합으로 가져지는 직사각형에 대해 카운트를 안해야 하는 부분인데

이걸 아무생각 없이 가능한 조건에 맞는 모든 (l, r, u, d)를 저장한 후 각 (l, r, u, d)에 대해 자신을 포함하는 직사각형이 있는가? 식으로 처리하면 O(n^4 * n^2 + (n^4)^2)으로 시간초과가 나야 하지만 데이터가 약해서 ac를 받는다.(?)

좀 더 똑똑한(빠른) 풀이에 대해 생각하기 위해 어떤 직사각형들이 답이 될 수 없어지는지에 대해 생각해보자.

결정할 부분은 왼쪽위 꼭짓점(l, u), 오른쪽 아래 꼭짓점(r,d)가 될텐데 만약 ( (l, r), (u, d) )가 정답이 된다면 ( (ll, rr), (uu, dd) ) (l<=ll,rr<=r,u<=uu,dd<=d)는 전부 정답이 될 가능성이 없다.

이를 효율적으로 처리하기 위해서 이미 처리한 ((ll, rr, uu, dd)를 다 지운) (l, r, u, d)에 속한 애들은 또 지워줄 필요가 없다.

그럼 이제 각 (l, r, u, d)를 정점으로 보고 최소한의 (ll, rr, uu, dd)에 대해 귀납적으로 다 처리되도록 정의하려면

f(l,r,u,d) = ( (l, r) (u, d)를 지우는 함수 )

f(l,r,u,d) = f(l+1,r,u,d) + f(l,r-1,u,d) + f(l,r,u+1,d) + f(l,r,u,d-1)로 표현 가능하다.

이미 방문한 (l,r,u,d)에 대해 중복으로 방문하지 않도록 처리한 후, 각 l, r, u, d에 대해 직사각형의 크기가 큰 직사각형들에 대해 먼저 처리를 해주면

O(n^4 * n^2 + n^4)에 문제를 해결할 수 있다.

코드

Gold

Bovine Genomics (Gold)

각 구간의 시작위치(i)를 결정하고 각 점박이 소들의 i에서 시작하는 유전정보에 대한 트라이를 구성한 후,

각 점이 없는 소들에 대해 트라이를 어디까지 따라갈 수 있는 지 구해준 후 그 중 최대값까지는 중복되는 문자열이 있다는 이야기이기 때문에

모든 i에 대해 min(최대값+1)를 구해주면 된다.

코드

Modern Art 2

각 색상에 대해 시작점과 끝점에 대한 인덱스가 겹치지 않는 괄호로 표현할 수 있다. (겹치는 인덱스를 갖는 경우는 같은색상인 경우 뿐)

각 색상에 대해 처음으로 나온 인덱스와 마지막으로 나온 인덱스를 구해준 후,

n개의 색상을 가지는 괄호에 대해 짝이 맞는지 / 가장 깊은 깊이가 몇인지 구해주면 된다.

코드