전체 글110 ACPC 2015 연습 결과 및 H. Capital City 풀이 대회 링크 : https://codeforces.com/gym/100676 결과 ACPC 2015 H. Capital City 문제가중치가 있는 무방향 그래프가 주어진다. 여기서 '사이클'이란, 어느 하나의 간선을 지워도 어떤 정점 u에서 정점 v로의 경로가 존재할 때에 u와 v는 같은 '사이클'에 속한다고 정의한다. 두 정점 사이의 거리는 다음과 같이 정의된다.1. 두 정점 u와 v가 같은 사이클 내에 속한다면, 둘 사이의 거리는 0이다.2. 두 정점 u와 v가 같은 사이클 내에 속하지 않는다면, 둘 사이의 거리는 둘 사이를 잇는 최단 경로의 길이이다.문제에서 요구하는 것은 다음과 같다. f(s)를 정점 s로부터 시작되는 최장 경로로 정의할 때, f(x)=min[f(s)]인 정점의 번호 x를 출력하는 .. 2016. 8. 30. 제 2회 삼성 대학생 프로그래밍 경시대회 본선 후기(SCPC 2016) 대회는 크게 이벤트 세션과 본 대회로 구성되었다. 1. 이벤트 세션오후 12시 ~ 12시 30분 동안 쉬운 영어 문제 하나를 푸는 이벤트가 있었다. 문제를 요약하면, N개의 나무가 있고 각각의 높이는 h(i)이다. 하루가 지남에 따라 모든 나무들은 길이가 1씩 자란다. 이 때, 각 날마다(매일) t(i) 높이에 레이저를 쏘아 높이가 t(i)를 넘는 나무들은 모두 t(i)가 되도록 자른다. 잘려지는 나무들의 길이의 총합을 구하는 것이 문제이다. O(N)의 간단한 풀이가 있지만, 문제를 보았을 때에는 O(N log N) 풀이를 떠올렸다. 하지만 맞추지 못하였는데, 문제를 푸는 시간 내에 Renumbering할 때의 배열 인자 부분에 코딩 실수가 있었던 것을 알아내지 못하였다. 이벤트 세션이 끝난 후, Dat.. 2016. 8. 19. Shortest Path Faster Algorithm The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the average case, it is likely to outperform Be.. 2016. 7. 28. 제 2회 삼성 대학생 프로그래밍 경시대회 2차 예선 후기(SCPC 2016) BOJ Camp 도중에 대회가 있어서 집중하지 못했다. Camp 문제들에 대한 참가자들의 질문에 답해주어야해서 힘들었다.오전에 잠깐 해서 1,2,3번을 짜고 오후엔 저녁 먹고 난 이후에 4번 푼 게 전부였다.1차와 달리 2차는 난이도가 많이 상승해서 다 풀지는 못했지만 만점자이신 dotorya님께 풀이를 다 설명들었다.4, 5번은 문제 서술조차 요약하기 힘들기 때문에 그냥 후기 형식으로 글을 남김, 문제를 푼 순서는 2번 - 1번 - 3번 - 4번이다. 2번은 정말 간단한 1차원 DP이기 때문에 별로 할 말이 없는데, 문제에 특이한 초기 조건을 읽지 못해서 3번이나 틀렸었다. 1번은 STL을 쓰면 계속 TLE가 나서 그 부분을 다 고치니까 간신히 만점이 나왔다. 3번은 직관적으로 가로선을 가장 아래에서부.. 2016. 7. 24. 제 2회 삼성 대학생 프로그래밍 경시대회 1차 예선 풀이(SCPC 2016) 1. 결과2. 해설 영상(5분에서 6분 사이에 D(i', j) = sum(D(i'-k, k))라고 했는데 D(i', j) = sum(F(i'-k, k))라고 봐주시면 감사하겠습니다.) 2016. 6. 30. 이전 1 ··· 10 11 12 13 14 15 16 ··· 22 다음
