[Codeforces 1113C] Sasha and a Bit of Relax XOR 개념에 대한 기본적인 지식이 필요한 문제이다. 전체 n개의 수가 주어지고 길이가 짝수인 어느 구간을 설정할 때 그 구간의 처음~중간까지의 수를 모두 XOR한 값과 중간 이후~끝까지의 수를 모두 XOR한 값이 같은 구간이 총 몇 개 존재하는지 카운트하는 문제이다. 이 문제를 풀기에 앞서 XOR이라는 연산의 특성에 대해서 생각해보자. XOR는 비트 차원의 연산으로 같은 자릿수의 비트 중에서 값이 다른 수가 단 하나라도 존재한다면 1이 되고, 모두 동일해야만 0이 되는 연산이다. 즉 a XOR b의 결과가 0이라면 a==b가 성립하고 이는 필요충분조건이다. 이를 확장해서 생각해보면 가 성립한다면 좌변과 우변의 값이 동일하다는..
[Codeforces 1133D] Zero Quantity Maximization - 1500 그닥 어려운 문제는 아니지만 stl을 잘 사용하는게 중요한 문제이다. 문제는 c=d*a+b=0을 만족시키는 특정 d값이 있을 때 그 d를 가지는 (a,b) pair가 최대 몇 개인지를 구하는 문제이다. 간단하게 생각해보면 a/b를 실수형으로 구해서 해당 a/b와 동일한 값을 가지는 pair가 총 몇개인지 구하면 되는데 a,b의 범위가 최대 10억씩이기 때문에 소수의 정밀도 오차문제가 생긴다. 따라서 단순하게 a에서 b를 나누는 방식은 위험하다. 그래서 나는 소수형태가 아닌 분자와 분모형태로 표현할 수 있는 분수로 표현해야 한다. 분수로 표현을 하기 위해서는 모든 분수를 기약분수의 형태로 표현해야 한다. 1/2나..
[Codeforces 1065C] Make It Equal 참 오랫동안 붙잡고 있었던 문제이다. 처음에는 바이너리 서치로 풀려고 해봤는데 시간이 터졌다. 그렇게 어떻게 풀어야 할지 일주일 넘게 고민하다가 결국 솔루션을 봤다. 솔루션은 '지금까지 소모된 cost'(=sum) + '현재 높이에서 새롭게 추가된 막대의 수'(=cnt[i])의 총합을 계산해서 k이하일 때는 계속 sum에 누적해나가고, k를 초과했다면 slice수를 추가하고, sum=cnt[i-1]로 두면 된다. 그리고 다음 높이(i-1)에서 소모되는 cost는 cnt[i-1]+=cnt[i]로 구할 수 있다.문제의 첫 번째 예시 입력처럼 1 2 2 3 4 가 있다고 가정해보자. 가장 높이가 높은 4부터 시작해서 그 다음 높이인 3에 도달했다고 하..
[Codeforces 1132C] Painting the Fence [1,n]구간의 펜스가 있고 총 q개의 painting(색칠) query가 들어온다. 이 q개의 query중에서 2개를 제외한 (q-2)개의 query만 선택해서 색칠된 구간의 수가 최대가 되도록 만드는 문제이다. 구간의 합과 관련된 문제라서 lazy propagation을 써야하는 문제 같았는데 그렇게 하면 시간복잡도가 O(N^2 * logN)시간이 아슬아슬하게 터진다. 게다가 이 문제는 c번 문제였고 푼 사람수도 꽤 있었기 때문에 어떻게든 더 간단히 풀 수 있는 방법이 있다고 생각했다. 콘테스트 당시에 생각한 풀이는 총 q개의 query중에서 색칠의 기여도가 가장 적은 2개의 query를 계산해내는 것이었다. 이러면 q개 중에서 2개..
[Codeforces 1118B] Tanya and Candies n일동안 하루마다 할당된 캔디의 수가 주어진다. 이때 어떤 하루의 캔디를 모두 삭제 한 뒤의 상태(그 이후의 날은 앞으로 한 칸씩 당겨짐)에서 홀수 날 캔디의 합과 짝수 날 캔디의 합이 같은 날이 n일 중에 몇 일인지 찾는 문제이다. naive하게 푼다면 i번째 날을 계산하기 위해서 1~(i-1)번 째까지 수 + (i+1)~n번 째까지의 캔디를 모두 더하면 되고, 이 풀이는 O(N^2)이다. 하지만 이 문제는 n이 최대 20만이기 때문에 시간이 초과될 것이다. 그래서 관건은 1~(i-1)번째까지, (i+1)~n번 째까지의 캔디의 합을 빨리 구해야한다. 당연하게도 Prefix Sum(부분합)으로 푸는 문제이다. 이 문제에서 한 가지 처리해주..
[Codeforces 1066B] Heaters 역시나 전형적인 그리디 문제이다. 처음에 풀 때는 문제 조건을 잘못 이해해서 한참 고생했다. '1'은 히터가 존재하는 위치일 뿐 전원은 꺼져있다고 간주해야하는데 나는 전원이 켜져있다고 생각해서 실제 정답보다 답을 적게 구했다.풀이는 간단하다. 왼쪽에서부터 오른쪽으로 가면서 현재 위치(cur)에서 가장 오른쪽에 있는 히터를 발견하면, 그 지점(i)을 기준으로 [i-r+1,i+r-1]은 heating할 수 있다는 의미이다. 그래서 나는 그 히터의 범위가 닿지 않기 시작하는 위치(=i+r)로 cur를 바꿔주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454..
[Codeforces 1110B] Tape 요즘 그리디문제를 자꾸 바이너리 서치로 풀려고 삽질하는 것 같다. 그리디 문제는 솔루션이 그리디라는 것만 알면 쉬운데, 확신이 없어서 헤매는 것 같다. 길이가 m인 긴 막대에 n개의 부서진 부분이 존재한다. 이 부서진 부분을 붙이기 위해 총 k개의 테이프를 사용할 수 있을 때(한 개당 테이프 길이는 상관없음) 필요한 총 테이프 길이의 최소는 얼마인지를 묻는 문제이다. 문제는 보기에는 바이너리 서치의 lower bound로 풀면 될 것 같은데 WA를 받았다. 아마 반례가 존재하는 모양인데 아직 정확히 왜 안되는지는 모르겠다. 아무튼 더 확실한 그리디 풀이법이 있으니 그리디로 풀자.사실 이 문제를 간단하게 표현하자면 n개의 인접한 수를 k개의 그룹으로 묶을 때 그룹..
[Codeforces 1070D] Garbage Disposal n일 동안 매일 a_i만큼의 쓰레기가 발생하고(0이면 발생 안함) 그 쓰레기를 크기가 k인 봉투에 담아서 버려야하는데, 오늘 발생한 쓰레기는 반드시 오늘 아니면 내일 안에 처리해야 한다. 이때 필요한 쓰레기 봉투의 최소 개수를 구하는 문제이다. 문제를 처음 풀 때는 맞왜틀을 외치다가 테스트케이스를 슬쩍 봤는데 내가 고려하지 않은 것이 있었다. 내 솔루션은 오늘과 내일의 쓰레기 양을 더한 값을 k로 나눠서 나머지에 따라서 ans를 계산했는데, 이 논리는 오늘 쓰레기가 내일까지 처리되지 않을 수도 있었다. 문제 제약조건상 오늘 쓰레기는 늦어도 내일까지 처리해야하기 때문에 내가 푼 솔루션은 잘못된 것이다. 그래서 올바른 솔루션은 오늘의 쓰레기 양..