티스토리 뷰

PS/Codeforces

Codeforces Round #407 (Div. 2)

박트리 2017. 4. 7. 22:24

A. Anastasia and pebbles


문제


Anastasia 에게 2개의 주머니가 있고 각 주머니에 최대 k개의 조약돌을 넣을 수 있다. 또한 한 주머니에는 한 종류의 조약돌만 넣을 수 있을 때 모든 조약돌을 줍는데 걸리는 최소 일자를 구하는 문제이다.



문제 풀이


매일 각 주머니에 최대한 넣는걸 반복하면 된다.

 

소스 코드





B. Masha and geometric depression


문제


b, q, l, m 이 주어졌을 때 보드에 적게되는 수열의 수를 구하는 문제이다.



문제 풀이


b가 0인 경우와 q가 -1, 0, 1 인 경우들을 잘 분리해서 구현하면 된다.

좀 더 생각해보면 q가 -1인 경우만 제외해서 구현하면 쉽게 구현할 수 있다.

싸이클을 체크하는 use set와 bad integer를 저장하는 s set 두개를 이용해서 구현하였다.

 

소스 코드







C. Functions again


문제


 과 같이 함수를 정의 하였을 때 주어진 범위 내에 가장 큰 f값을 구하는 문제이다.



문제 풀이


\(O(N)\) DP풀이도 있지만 버추얼 중에는 \(O(NlgN)\) 분할 정복 풀이를 떠올렸다.

왼쪽 부분 문제에서 푼 답, 오른쪽 부분 문제에서 푼 답, 중앙을 거치는 부분 문제에서 푼 답을 정복하면 된다.

 

소스 코드







D. Weird journey


문제


n개의 정점, m개의 간선이 있을 때 m-2개의 간선은 2번 지나가고 2개의 간선은 1번 지나가는 경우의 수를 구하는 문제이다.



문제 풀이


양방향 간선을 단방향 간선 2개로 생각하면 m개의 간선을 2번 지나는 방법은 오일러 서킷으로 쉽게 생각할 수 있다.

2개의 간선을 어떻게 끊느냐는 건데 이 또한 오일러 트레일을 생각하면 된다.

임의의 정점에서 연결된 다른 정점중에 2개를 뽑는다. 이 중 하나에서 그 정점의 서브트리로 오일러 서킷을 만들수 있다.

마찬가지로 다른 정점에서 시작하는 오일러 서킷을 만들고 이 둘을 현재 정점으로 합치면 문제가 요구하는 조건을

만족 시킨다. 따라서 모든 정점에 대해서 간선들의 수에서 2개를 뽑는 경우의 수 만큼 good path를 만들 수 있다. 

여기에 추가적으로 자기자신을 가리키는 간선만 고려하면 되는데,

2개의 간선을 모두 자기자신을 가르키는 간선을 고르면 가능하기 때문에 다시 2개를 뽑는 만큼 가능하고,

한 개는 자기자신을 가리키는 간선과 한 개는 다른 정점을 가르키는 간선을 뽑는 것도 가능하다.

위 3가지 경우를 dfs하면서 구하면 된다. 

 

소스 코드









E. The Great Mixing


문제


주어진 코크들을 적중절히 혼합해서 농도 n을 만드는데 사용하는 가장 적은 수의 코크를 구하는 문제이다.



문제 풀이



주어진 문제를 위와 같은 식으로 변경할 수 있다. 각 항의 범위는 -1000 ~ 1000 까지 가능하고 항의 개수는 k를 넘지 않기 때문에 
비둘기 집 원리에 의해서 2000개로 항의 개수를 줄 일 수 있다. 모든 항의 합을 정점으로 각 항의 계수를 간선으로 생각하고 bfs하여
0번 정점에 2번째 도달하였을 때를 구하면 되는 문제로 바뀐다. 

소스 코드



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함