노력하는 공대생의 공부일지

문제를 요약하면, 수열에서 인접한 두 수를 골라 1빼는 연산을 원하는 만큼 시행하여 수열의 모든 원소를 동일하게 만들 수 있도록 하는 수열의 개수 단 hi는 0이상 Hi이하 정수라는 제한 조건이 달려있다. 저 연산을 뚫어지게 살펴보면 다음과 같은 관찰을 할 수가 있다. h를 결정했다고 치고, 최종적으로 같아지게 되는 수열의 원소 값을 x라고 두면, 이 연산을 시행해서 모든 원소를 x로 만들 수 있는지를 판단하기는 쉽다. a(i)=h(i)와 h(i+1)을 골라 연산을 시행하는 경우의 수. 라고 정의하자 x=h(1)-a(1)가 되어서, a(1)가 고정된다. 그런데, x=h(2)-(a(1)+a(2))이므로, a(1)이 결정되면 a(2)도 결정된다. (지금 상태에서 h와 x는 상수이므로) 마찬가지로 모든 a값들..

야구를 너무 많이 자주 본다 게임을 너무 자주 많이 한다 인생이 낭비되고 있는 느낌이다... ps도 별 다를거 없지만 위의 2개는 남는게 없는거 같다. 일단 요번주 현대모비스 예선이랑 ucpc예선 떨어지면 우울해서 술 마실듯..

오늘 오프라인 동적 연결성 판별에 관해서 공부하면서 문득 느낀 점이 있어서 적어본다. 나는 중급알고리즘 까지는 거의 다 학습했고 꽤 오래전부터 공부해오고 있는데 새로운 알고리즘 개념 ( segment tree,kmp등등 여러가지.... )을 공부할 때 코드를 절대 보지 않는 것이 더 도움이 되는거 같다. 나는 대충 팀노트 복붙하면 되지 라는 마인드로 예전에 남의 코드를 베이스로 공부를 좀 했었는데 의미가 별로 없는 작업들인거 같다. 세그먼트 트리에 대해서 배운다고 가정을 하면,[구간을 로그 바운드로 쪼개서 관리한다] 라는 개념과 쿼리처리와 업데이트에 대해서 개념만 공부를 하고 구현하는 과정에 있어서는 혼자 힘으로 아무것도 보지 않고 직접 자기가 구현을 생각해서 타이핑 해보는게 더 도움이 되는거 같다. 물..

어제 대회에서 나온 문제 https://codeforces.com/contest/1700/problem/C 대회 때는 그리디가 될거 같았는데, 자꾸 최근에 글을 올렸듯이 차이를 보는 것이 생각이 나서, 그렇게 생각을 하다보니까 조금 오래걸렸다. 이 문제도 차이를 보는 방식으로 하면 쉽게 풀린다. 왜 그렇나면, 연속된 구간에 1을 더하거나 전체 구간에 1을 빼는 방식은 다루기 까다롭다. 그런데, 현재 i번째 값과 i-1번째 값의 차를 새로운 dif[i]로 정의하면 쉽게 풀수가 있는데, 1~i까지 1을 더하는 방식은 dif[1]에 1을 더하고 dif[i+1]에 1을 빼는것과 동일하고, i부터 n까지 1을 더하는 것은 dif[i]에 1을 더하는 것과 동일하기 때문이다. 그리고 전체 구간에 1을 빼는 것은 di..

사실 별건 아닌데, 내가 애초에 세그 트리를 비재귀로 구현하다 보니가, 레이지가 너무 안 익숙해서 정리한다. 레이지는 대부분 재귀로 구현하고 (비재귀 방식도 있다고는 한다...) 그렇다 보니까 구현도 길어지고 그러는데, 나중에 scpc같은 곳에서 팀노트 없을 때 빠르게 구현해 낼 자신이 없을 때 가끔 써먹어야 겠다... 아 근데 (금광 + 레이지) 세그 비재귀로 짤때는 잘 써먹고 있다. 시간복잡도는 O(nloglogn)인데, 다음과 같은 방식을 이용한다. 1. 업데이트: 구간 [L,R]에 c만큼 더하기. 세그트리 base이기 때문에 최대 특정 길이의 구간은 logN개의 노드로 분할된다. 현재 노드를 x라 하자. 이 노드에 다음과 같은 작업을 할 것이다. 이 노드의 자식 노드들을 업데이트 하지는 않는다. ..

도 땄다. 다행이다!

최근 코포에서 이런 문제가 나왔었다. https://codeforces.com/contest/1687/problem/C 어려운 문제였는데, 아이디어 자체가 발상적이기도 하고 몇번 본거 같아서 적어본다. (사실 대회때는 나올때마다 틀렸음.) 두 수열에 관한 연산을 시행할 때 두 수을 보는게 아니라, 두 수열의 차이를 보자. 라는게 핵심 아이디어 이다. 위의 관찰만 하게 되면, 구간의 연산들이 어떻게 바뀌는지 쉽게 살펴볼 수 있다. 두 구간의 합이 같을 때, Ai=Bi를 시행하는 것은 Ci=Ai-Bi라는 수열을 생각하면, Ci의 구간합이 0이되는 구간에, Ci들을 전부 0으로 바꿔준다는 것이다. 이를 이용하면 문제가 새롭게 바뀌게 되고, 쉽게 풀린다. https://codeforces.com/problems..

술을 마신 김에 써본다. 오늘은 5월 14일 청정수컵 본대회가 있던 날이었다. 대회 후기같은 경우는 dong_gas 의 블로그를 참고해주기를 바란다. 드디어 코드포스 오렌지를 찍었다. 나는 개인적으로 코드포스 블루 이상부터, 어느정도 알고리즘 공부를 했고, 알고리즘 문제 풀이 능력이 뛰어난 사람으로 인식하기 시작한다. 내가 오렌지를 찍는데는, 코드포스를 시작한지 21개월, 알고리즘 문제풀이를 시작한지 대략 2년 하고도 2개월 정도가 걸렸다. 코드포스 오렌지는 고수와 중수의 경계선 부근이라고 나는 생각한다. 오렌지와 레드간의 간격이 되게 넓고 크기에, 그 간격을 뚫기가 매우 어려워, 많은 수의 고수 분들이 오렌지에 머물러 있고는 한다. 그래서 나같은 "가짜 오렌지"와 "진짜 오렌지"의 차이가 명확하게 드러..

gold 에 있는 n binary search 불가 Q : 시작점을 고정시켰을 때 길이가 클 수록 좋은 구간의 값은 커지는가? A : 커진다. 그렇다면 다음 2가지 sub문제로 바꿔보자. 1. 특정 구간이 주어졌을 때 이 구간이 좋은 구간인지를 어떻게 판정할 것인가? 2. 좋은 구간이 주어졌을 때 이 구간의 값을 어떻게 판정할 것인가? 1번은 의외로 쉽게 할 수 있는데, 구간을 정렬하고, 앞에서 부터 합쳐주면서 홀 수 component가 되지 않으면 된다. 이 풀이의 정당성은 쉽게 증명 된다. 2번도 1번에서 파생되어 나온다. 합쳐나가면서 마지막으로 남는 수가 구간의 값이라는 것을 쉽게 알 수 있다. 그렇다면 본 문제를 풀어보자. 이제 핵심 아이디어는 1~39 까지 i를 순회하면서 i가 1일때는 연속된 ..

를 땄다. 이 자격증은 왜 존재할까. 실기를 따야겠다... 응시료 78000원이라 열심히 공부해야겠다.