Codeforces Round #831

Dashboard - Codeforces Round #831 (Div. 1 + Div. 2) - Codeforces

A - Factorise N+M

M = N == 2 ? 2 : 3;

00:01 AC

단순히 N을 다시 출력해도 된다.

 

B - Jumbo Extra Cheese 2

감이 전혀 안 와서 C로 넘어갔다가 다시 돌아왔다.

나만 못 풀고 있어서 멘탈이 살짝 흔들렸다.

 

한참 고민하다 다음과 같은 식을 도출하였다.

ans = 2 * (xsum + ymax)

단 하나의 치즈만 a와 b가 모두 사용되고 나머지 치즈는 둘 중 하나만 사용됨을 알 수 있다.

ymax를 고정하면 각 치즈에 대하여 a와 b 중 무엇을 x로 사용할 것인지 결정할 수 있다.

 

ymax를 선택할 때는 a와 b 중 최댓값만 고려하면 된다.

편의를 위하여 a가 b보다 작다고 가정한다.

a 대신 b를 선택하면 모든 치즈에 대하여 y 제한이 완화된다.

일부 치즈를 회전시킬 수 있다면 둘레가 감소하며 그러지 못하더라도 둘레는 기존과 동일하다.

따라서 ymax를 선택할 때는 b만 고려하면 된다.

 

이제 모든 치즈를 b가 큰 순으로 정렬하자.

각 치즈마다 ymax를 b로 고정하고 둘레를 구하면 된다.

사용이 끝난 치즈는 다음 치즈를 위하여 회전시켜준다.

 

00:46 AC

 

B를 푸는 데 30분이 넘게 걸렸다.

나는 엄청 어려웠는데 다들 금방 풀더라.

 

다른 사람들의 풀이를 보고 알게 된 놀라운 사실은 ymax가 항상 bmax라는 것이다.

위의 풀이에서 정렬 이후 과정을 잘 살펴보면 초기 둘레에서 더 이상 둘레가 작아질 수 없음을 확인할 수 있다.

새로운 둘레는 기존 둘레에서 이전 치즈의 a를 빼고 현재 치즈의 b를 더하여 구할 수 있다.

이때 이전 치즈의 a는 현재 치즈의 b보다 클 수 없으므로 둘레는 작아질 수 없다.

 

참고로 나는 치즈를 못 먹는다.

모든 치즈를 못 먹는 것은 아니고 먹을 수 있는 치즈가 한정된다.

너무 느끼해서 구역질이 난다.

 

계속 생각해보니 이제는 최댓값을 ymax로 놓는 것이 당연해 보인다.

최댓값은 무조건 둘레에 포함되니까 차라리 y 쪽으로 빼는 것이 이득이다.

많이 풀어보면 이런 것도 바로바로 보이나보다.

 

C - Bricks and Bags

1번 가방에는 가장 가벼운 벽돌을 넣는다.

2번 가방에는 가장 무거운 벽돌을 넣는다.

3번 가방에는 나머지 벽돌을 모두 넣는다.

이후 3번 가방에서 2번 가방으로 벽돌을 하나씩 옮기면서 답을 찾으면 된다.

00:52 WA

반대로도 똑같이 해주면 된다.

00:55 AC

 

D - Knowledge Cards

시작점에서 도착점으로 가는 경로만 비워져 있다면 가능하다고 생각하였다.

01:07 WA

더 관찰해보니 시작점과 출발점을 포함하여 4개의 셀만 비워져 있다면 가능해보였다.

01:11 AC

 

E - Hanging Hearts

리프 노드부터 따라 올라가는 단순한 그리디 풀이를 제출하였다.

01:23 WA

현재 노드를 사용하는 경우와 사용하지 않는 경우로 나누어서 트리 dp를 하였다.

현재 노드를 사용하려면 모든 자손 노드에 대하여 최대 1개의 자식 노드만 사용해야 한다.

단순히 노드의 레벨을 구한다고 생각하면 된다.

현재 노드를 사용하지 않는다면 모든 자식 노드에 대한 dp 값을 합하면 된다.

증명이 확실하지는 않지만 믿음을 가지고 제출하였다.

01:46 AC

 

대회 중에는 재귀 dfs 코드로 작성하였다.

문제 조건에 의하여 dfs 없이 반복문으로 처리할 수도 있다.

이는 특수한 형태의 위상 정렬이라고도 볼 수 있다.

 

F - Conditional Mix (not solved)

한참 고민하다 놀라운 발상이 떠올라 열심히 dp 코드를 작성하였다.

대회 종료 10분 전 코딩을 끝냈는데 예제가 나오지 않았다.

그때서야 발상 자체가 틀렸다는 것을 깨달았다.

어려운 문제 같아서 일단 넘어가려고 한다.

 

G - Dangerous Laser Power (not solved)

Pass

 

H - MEX Tree Manipulation (not solved)

Pass

 

I - Arranging Crystal Balls (not solved)

Pass

 

끝

끝