pseong

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만 개라 말도 안 되는 것이다. 계속 어떻게 해야 과거의 세그먼트를 꺼내서 답을 구할 수 있을까 생각했는데 답은 간단했다. 쿼리가 들어올 때 전부 쿼리 순서대로 쿼리를 저장한다. 그리고 과거의 세그먼트가 필요하다면 필요한 과거의 세그먼트와..

Problem - E - Codeforces codeforces.com 간단한 문제지만 업솔빙에 시간이 좀 걸려서 정리. 최소의 비용을 찾기 위해선 d(a)가 작아져야하고 m(a)가 커져야 한다. 잘 생각해 보면 m은 d보다 커질 수 없다. m이 커지려면 0부터 m-1까지의 숫자가 배열 a에 존재해야 한다.0부터 m-1까지의 숫자가 존재하면 d는 m이 되어버리기 때문이다. 반대로 d는 m보다 커질 수 있다. m보다 큰 숫자가 존재하면 d의 값이 1이 증가하기 때문이다. 결국 문제를 요약하자면, 배열 a에서 m값보다 큰 숫자 종류의 개수가 문제에서 정의하는 비용이다. m값보다 큰 숫자 종류를 줄이기 위해서는 m값을 크게 키우면 된다. 이는 배열 a의 어떠한 값을 m으로 바꿔 준다면 m값은 1이 증가하게 된..

Problem - C - Codeforces codeforces.com 쉬운 문젠데 어마어마한 실수를 했다. 기존 배열을 복사를 해서 1번째 행부터 n번째 행까지 확인하면서 스왑 할 두 개의 인덱스를 찾으면 되는데 중간쯤에 스왑해야 하는 부분을 찾으면 이전 행에도 적용해야 하는걸 간과하고 이후에만 스왑을 적용했다. 결과적으로 테스트 케이스는 맞았으나, 당연히 저격 데이터는 있을 것이고 그렇게 틀렸다. 맞왜틀 하루하고 버리고 오늘 다시 봤는데 이런 어마어마한 실수였다. 이전 사건에도 영향을 미치는지 잘 판단해야 할 것 같다.

Problem - D - Codeforces codeforces.com 그냥 구현 문젠데 어려워서 정리 잘 관찰만 하면 되는데 그게 어려운 문제 행과 열을 각 각 따로 계산해서 더해줘야 한다. 행에서는 m개의 요소가 계속 돌면서 채워주기 때문에 행 카운트는 항상 단조 증가한다. m개의 요소가 계속 돌기 때문에 만약 안 채워져 있으면 카운트를 1 증가시켜주고 채워주면 된다. 열에서의 관찰이 조금 어려웠는데 일일이 1이 들어오는 경우의 수를 따지다 보니까 굉장히 문제가 어려워졌다. 사실 열에서도 m개의 요소가 사이클을 도는 건 맞지만 한 번 돌 때마다 새로운 m개의 요소가 앞에 추가가 된다. m개의 요소가 사이클을 도니까 m번마다 열 카운트가 반복될 것이다. 반복될 때마다 새로운 요소 한 줄이 맨 앞에 붙으..

F - Ignore Operations AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp dp [i][j] : i개까지 문자를 봤을 때 변환되는 문자의 길이를 j라고 할 때의 경우의 수 라고 놓고 문제를풀면 잘 풀리지만 최적화를 해야 풀린다. 그냥 dp 채우면 O(N^3)이다. 1. 1차원 또는 2차원 또는 3차원 dp 상관없이 dp를 바텀업으로 채울 때 중간에 어떤 연속적인 값을 더하는 구간이 존재한다면 dp를 채우면서 prefix_sum을 이용하면 연속적인 숫자의 방향의 개수에 따라 그 개수만큼 시간 복잡도의 차수를 줄..