Codeforces(500): Good Bye 2014 후기

2014. 12. 31. 03:40알고리즘 문제풀기/대회 참가기

A번.

그냥 위치가 x에 있으면 x+(a_x) 로 이동한다는 말 같아서 대충 했더니 잘 된거같다.

B번.

연결되어있는 수(=교환할 수 있는 수)들을 BFS로 묶고, 정렬해서, 재배치하고, 끝.

그런데 지금 보니까 시스템 테스트 통과를 못했다. 어...?

C번.

첫 번째로 읽을 책과, 나머지 책들을 생각해보자.

첫 번째 책이 중간에 꽂혀있으면, 그걸 다 들어내고 읽어야 하고, 결국 나머지 책들의 순서는 그대로인채 첫번째 책만 제일 위에 놓이게 된다.

그러면 애초에 아무것도 안 드는게 이득이겠지? 그래서 첫 번째로 읽을 책은 제일 위에 가야 한다.

두 번째로 읽을 책을 찾기 위해 다른 책들을 들어낼 때도, 어차피 그 두번째 책이 어디에 꽂혀있었든 결과는 같다.

그렇다면 최소한으로 책을 드는 것이 최적이겠고, 첫번째 책이 방금 올라왔기 때문에 두번째 책은 그 바로 밑에 놓자.

이런 식으로 논리를 전개해나가고, 깊게는 생각하지 않고,

읽을 계획 목록의 책들중에 처음 나오는 책들만 순서대로 출력하였다.

사실 좀 자신이 없었지만 pretest를 통과하고 나니까 빨리 넘어가야겠다는 생각에 넘어왔다.

D번.

트리상에 세 산타가 각각 서로 다른 창고를 한 사람당 하나씩 정하려고 한다. 산타들은 모든 창고들의 조합(a,b,c나 d,e,f나 ...)중 하나를 서로 동등한 확률로 선택할 것이다. 이때 d(a,b)+d(b,c)+d(c,a)의 기댓값을 구하는 문제이다.

전체 가짓수가 개라는건 당연하니까, 각각의 간선이 몇번 더해지는가를 세어보자는 생각이 들었다.(이런 문제가 IOI에 traffic이라는 문제가 있었던거 같은데...)

각각의 간선은 한쪽에 a,다른쪽에 (n-a)개의 정점이 있다고 하면,

산타들이 한쪽에서 두 개, 다른쪽에서 한 개의 정점을 고르면 이 변은 세 길이의 합에 두 번 들어간다.

그렇기 때문에 tree DFS를 통해서 각 노드의 children 갯수만 세어주면 한쪽 정점의 갯수가 나오기 때문에, 이를 a라고 하면 임의의 간선에 대해서 그 간선에 의해 기댓값은

만큼 커짐을 알 수 있다.

모든 간선을 돌면서 이 값을 더하고, 간선이 변할 때마다 이 값의 변화를 계산해서 출력해주면 된다.

E번.

p+l값 순으로 정렬한 도미노들을 a라고 하자.

도미노들을 오른쪽에서부터 왼쪽으로 돌면서, 나의 p보다 p+l값이 큰 것이 a에 있으면,

'그 도미노가 쓰러졌을 때 가장 마지막에 넘어질 도미노'로 나를 기록하고, a에서 빼버린다.

이후 다시 오른쪽에서 왼쪽으로 돌면서, '가장 오른쪽에 있는 도미노가 넘어지도록 하는 최소 비용'을 가지고 dynamic 배열을 채운다.

그후 i,j 쿼리가 들어오면 dyn[i]-dyn[j]를 출력했다.

지금 깨달은 가장 큰 문제점으로는,

dyn배열이 항상 내림차순이 아닐 수 있다는 것이다...



'알고리즘 문제풀기 > 대회 참가기' 카테고리의 다른 글

ICPC Seoul Regional 2018  (4) 2018.11.04
UCPC 2018 후기  (0) 2018.07.30
NYPC 1회 후기  (1) 2016.10.29
Codeforces(618): Wunder Fund Round 2016 후기  (2) 2016.01.30