pseong

Problem - E - Codeforces codeforces.com 노드 1에서 노드 n까지 가는데 걸리는 최대 시간을 최소로 단축시키는 문제다. 따라서 여행자 p는 최대 시간으로 노드 1에서 출발하여 노드 n까지 간다고 할 수 있다. 어떤 노드 x에서 인접한 노드가 a, b, c 3개가 있다고 가정해보자. 노드 a에서 노드 n까지 최단시간을 3 노드 b에서 노드 n까지 최단시간을 2 노드 c에서 노드 n까지 최단시간을 1 라고 하자. 다익스트라로 모든 노드에서 노드 n까지 가는데 걸리는 최단시간을 구할 때 노드 x에 접근하는 최초의 경로는 c일 것이다. 노드 x에서 c로 가려면 a로가는 경로와 b로가는 경로를 지워야 하므로 노드 x에서 c로 갈 때 걸리는 시간은 3이다. 다음에 접근하는 경로는 b이..

Problem - D2 - Codeforces codeforces.com 그래프 그리디 문제인데 굉장히 관찰이 어렵다. 가장 멀리서 쿼리를 날려야 거리가 중복되는 노드들이 가장 작아지므로 먼저 리프 노드를 쿼리로 날려야 한다는 것을 알 수 있다. 따라서 간단하게 모든 리프 노드를 전부 쿼리를 날리면 찾고자 하는 노드 x를 알 수 있을 것이다. 하지만 우리는 쿼리의 개수를 줄여야만 한다. 어떤 한 노드 y 기준으로 차수가 k라고 하자. 그 노드 y에 인접한 노드가 찾고자 하는 노드 x라고 한다면 그 노드 y의 서브 트리 (차수)를 k라고 한다면 굳이 k개의 서브 트리에서 쿼리 노드가 다 있을 필요는 없고 k개의 서브 트리에서 1개를 뺀 k-1개의 서브 트리에서만 쿼리 노드가 있으면 된다. 여기서 쿼리 노드..

Problem - E - Codeforces codeforces.com 어떤 한 셀에서 인접한 4개 이하의 셀들에 대해 자기 자신보다 값이 작은 셀이 존재한다면 그 셀까지 경로는 존재한다. 만약 어떤 한 셀의 인접한 4개 이하의 셀들이 전부 자기 자신보다 값이 클 경우 그 셀을 에러 셀이라고 하자. 에러 셀이 0개인 경우는 답이 0이다. 에러 셀이 1개 ~ 8개 사이인 경우는 답이 1 또는 2이고 에러 셀이 8개보다 클 경우 답이 2이다. 에러 셀이 1개 ~ 8개 사이인 경우를 체크해 줘야 하는데 두 개의 셀이 스왑 했을 때 상태변화가 일어나는 셀은 바뀐 셀의 인접한 8개의 셀들이다. 따라서 만약 1번 스왑만에 모든 셀들이 에러가 아니게 만들려면 무조건 스왑 하는 두 셀 중 한 셀은 어떤 에러 셀의 인접..

F - Cumulative Cumulative Cumulative Sum AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp Dx 에 대한 식을 Ax Bx Cx 순서대로 만들면 쉽게 만들어 진다. 하지만 mod때문에 엄청 헤멨다. 이 문제는 mod 지옥이다.. 엣코더에서 mod 라이브리러리를 지원한다. 하지만 그것을 쓰게 되면 내가 쓰고있는 세그먼트 트리 템플릿도 수정 해야되고 무튼 여러모로 귀찮다. 그렇다고 mod 템플릿을 따로 만들자니 굳이 만들 필요가 있을까 싶기도 하다. 이 문제로 인해 mod 연산을 빠트리지 않게 많..

Problem - D - Codeforces codeforces.com D를 이분 탐색 안 하고 풀 수 있길래 적어본다. 먼저 파이프를 맨 앞쪽부터 여는 게 가장 좋은 방법인 건 그냥 바로 알 수 있다. 그러면 답은 간단해진다. x개를 열었을 때 모든 버킷을 채우기 위해 걸리는 시간을 x = 1부터 나열해 보면 1개 열었을 때 걸리는 시간 2개 열었을 때 걸리는 시간 3개 열었을 때 걸리는 시간 ... n개 열었을 때 걸리는 시간 이 수열은 증가하지 않는 수열이다. 따라서 t초안에 모든 물을 채우게 할 수 있는 최소의 파이프의 수를 이분 탐색으로 해결할 수 있다. n개를 열어서 모든 버킷을 걸리는 시간보다 더 적은 t가 주어질 경우에 답이 없으므로 -1이 답이다. 이 구문을 잘 생각해 보면 어차피 더 적..

https://codeforces.com/contest/1688/problem/D codeforces.com 조금 긴 방법으로 구현해서 풀었는데, 자꾸 WA가 나오길래 풀이를 좀 더 간편하게 해서 업 솔빙을 해봤다. 그래도 WA가 뜨길래 더 이상 코드를 짧게 할 구간도 없고 long long 도 써서 문제가 없었다. 하지만 long long을 전부 썼지만 첫 입력인 원소의 개수 n는 int로 받았었다. 중간에 1부터 n까지의 합을 구할 때 n을 제곱을 한 것이었다. ( 당연히 오버플로우.. ) 고치고 AC. 다음부터는 원소의 개수를 받는 변수도 오버플로우를 잘 생각해야겠다. 문제 풀이는 간단하다. k가 n보다 작으면 길이가 k인 최대 구간을 구하면 된다. k가 n보다 클 때가 문제인데, 잘 생각해보면 처..

Problem - D - Codeforces codeforces.com 이것도 풀 수 있었는데 못 풀었다. 풀이는 맞았는데 구현에서 애먹다가 펑! 20분 정도만 더 줬으면 AC 받을 문제였다. 세그먼트 트리로 그냥 풀면 되는데 배열에서 자기 자신보다 큰 가장 가까운 원소 찾는 것을 그냥 스택을 써서 구현하면 되는데 멀티 맵을 써서 구현하다가 시간 다 까먹었다. 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이문제를 풀었으면서 왜 이상하게 구현을 했는지 모르겠다. 일단 이번 D문제의 풀이는 간단하다. 세그먼트 트리는 2개..

F - Operations on a Matrix AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 세그먼트 트리 하나로 쿼리들을 관리하고, 질의가 들어왔을 때 과거의 세그먼트 트리가 필요한 것 까지는 알았다. 하지만 과거에 세그먼트 트리를 전부 저장하면 되지 않을까 생각했는데, 쿼리가 20만 개라 말도 안 되는 것이다. 계속 어떻게 해야 과거의 세그먼트를 꺼내서 답을 구할 수 있을까 생각했는데 답은 간단했다. 쿼리가 들어올 때 전부 쿼리 순서대로 쿼리를 저장한다. 그리고 과거의 세그먼트가 필요하다면 필요한 과거의 세그먼트와..