제1회 곰곰컵

제1회 곰곰컵

서론

그냥 어쩌다 보니 풀었다.

 

A - 치킨댄스를 추는 곰곰이를 본 임스

단순 수학

 

B - 인사성 밝은 곰곰이

set

 

C - 곰곰이의 식단 관리

수학

 

D - 결전의 금요일

dp

 

E - Yes or yes

dfs

 

F - 숲속에서 새 구경하기

처음에는 Segment Tree로 풀었는데 더 쉬운 풀이가 존재한다.

답이 t라는 것은 새 3마리 중 적어도 1마리가 시점 t에 등장하였다는 것을 의미한다.

따라서 새 3마리에 대하여 lcm(Av, Bv, Cv) 미만의 시점 중 주기의 시작점만 고려하면 된다.

bfs를 이용한 더 빠른 풀이가 존재하지만 설명은 생략한다.

 

G - 합주단 곰곰

두 단원이 식사를 할 확률은 1 / K이다.

따라서 답은 N * (N - 1) / 2 / K가 된다.

 

H - 곰곰이의 심부름

먼저 dfs를 돌려서 이동 경로를 구하자.

cnt1 = 방문한 정점의 개수

cnt2 = 두 번 방문한 정점의 개수 + 1

답은 cnt1 * (cnt1 - 1) / 2 + cnt2 * (cnt2 - 1) / 2가 된다.

 

I - 곰곰이와 자판기

역순으로 업데이트하면 된다.

 

J - 보드 뒤집기 게임

뒤집기 마법을 사용해도 각 행과 열의 parity는 변하지 않는다.

 

K - 도박사 곰곰

dp[i][j] = 1번부터 i번까지의 카드 j장을 사용할 때 곰곰이가 이기도록 하는 카드 조합의 수

상태의 개수가 O(NM)개이고 각 상태 전이 횟수는 O(maxv)번이므로 TLE를 받는다.

누적 합 배열을 정의하거나 점화식을 아래와 같이 변형하여 해결할 수 있다.

dp[i][j] = dp[i][j - 1] + (1번부터 i번까지의 카드 j장을 사용할 때 곰곰이가 이기도록 하는 카드 조합의 수)

이때 정답은 dp[M][N] - dp[M][N - 1]이 된다.

 

끝

끝