#USACO 2016 January Contest

Bronze

Promotion Counting

플레티넘에 이전 응시수와 현재 응시수를 보면 몇 명이 골드에서 올라왔는지 알 수 있다.

앞을 참고해 골드에 이전 응시수와 현재 응시수를 보면 몇 명이 실버에서 올라왔는지 알 수 있다.

앞을 참고해 실버에 이전 응시수와 현재 응시수를 보면 몇 명이 브론즈에서 올라왔는지 알 수 있다.

source

Angry Cows (Bronze)

시뮬레이션 해서 최대값을 구해주면 된다.

source

Mowing the Field (Bronze)

좌표제한이 -2천~2천이기 때문에 맵을 만들어서 처리해도 되지만 생각이 귀찮아서 set을 이용해 구현했다.

시뮬레이션 하면서 각 좌표에 마지막에 방문한 시점을 저장해주자

현재 방문한 점이 이전에 방문한적 있다면 시간의 차이를 답에 갱신해주자

source

Silver

Angry Cows (Silver)

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

답을 X로 결정했을 때 차이가 2X아래로 난다면 그 구간에 있는 더미들은 다 폭파시킬 수 있다.

그리디하게 앞에서부터 폭파시켜주자.

source

Subsequences Summing to Sevens

연속된 숫자의 합이 7로 나누어 떨어지는지 판별하는 문제이기 때문에 각 숫자들을 그대로 가지고 있을 필요가 없고 7로 나눈 나머지만 가지면 된다.

어떤 임의의 [s, e]가 7로 나누어 떨어지기 위해서는 0~s-1까지의 합에 대한 나머지와 0~e까지의 합에 대한 나머지가 같아야 한다.

이를 이용해 쉽게 처리할 수 있다.

source

Build Gates

맵을 만들어서 처리해줄 수 도 있지만 맵을 만들기가 매우 귀찮다.

그래서 다른 방법을 생각해보니 영역이 하나가 생기기 위해서는 나갔다가 다시 들어올 때 생긴다.

따라서 나갔다 들어오는 횟수를 카운팅 해주자

그리고 좀 더 정밀한 처리를 위해서 두 칸씩 이동해주는식으로 처리하면(단위 길이를 0.5로 두면) 나갔다 들어오는 길이가 1인부분도 처리해줄 수 있다.

다른사람들의 코드를 보니 평면그래프의 정점과 간선사이의 성질을 이용해 문제를 풀었다.

source

Gold

Angry Cows (Gold)

일단 답 X가 가능하다면 X이상은 다 가능하다는 성질을 이용해 파라메트릭 서치를 돌릴것이다.

그리고 우리는 딱 한번만 폭탄을 터트린다는 사실도 알고 있다.

L[i] = i의 왼쪽을 다 터트리기 위해 i가 터져야 하는 최소 위력

R[i] = i의 오른쪽을 다 터트리기 위해 i가 터져야 하는 최소 위력

이라 정의하고 L[i]의 점화식에 대해 먼저 생각해 보자.

L[i] = min(L[j] +2, a[i] - a[j])

위 점화식에서 볼 수 있듯이 L[i]는 단조증가함을 알 수 있다. 또한 a[i]-a[j]값은 단조 감소한다. 그리고 이는 L[i]의 값에 대해 잘 생각해보면 a[i]-a[j]에 영향을 받는다.

따라서 L[i]를 구할 때 j에 대해 위로 볼록한 컨벡스를 이룬다.

이를 이분탐색으로 처리해줘도 괜찮다.

하지만 좀 더 생각해보면 i가 증가함에 따라 선택되는 피봇j는 단조증가함을 알 수 있다.

따라서 L[i]를 O(n)에 구할 수 있다. R[i]도 마찬가지의 원리로 구해줄 수 있다.

파라메트릭서치로 x를 결정해 준 후 각 구간에 대해 2x이하의 차이가 나면서 L[왼쪽], R[오른쪽] <= x-1인 구간이 존재하는 지 판별해주면 된다.

처음에 입력을 받을 때 각 위치를 2씩 곱해주면 처리가 좀 더 간단해진다.

source

Radio Contact

D(i)(j) = 사람1이 i만큼 이동했고 사람2가 j만큼 이동했을 때 최소 비용

으로 정의한 후 심플디피를 풀어주면 된다.

source

Lights Out (Gold)

시뮬레이션을 어떻게 잘 할지 묻는 문제이다.

각 점에대해 오목각인지 볼록각인지 저장을 해준 후 가능한 모든 구간에 대해 동선을 해싱을 하든 문자열로 표현하든 표현을 해주자

그리고 각 점에대해 시계방향으로 진행시키면서 이 구간이 다른 구간과 같은 동선을 가지는 구간인지 판단해주고 만약 유니크하다면 루프를 나와서 바로 빠른길로 가주면 된다.

최단거리와 방금 시뮬레이션으로 얻은 결과와의 차이의 최대값을 출력해주면 답을 구할 수 있다.

source