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

재밌는 문제였다. 이 문제를 전날 자기 전부터 고민해서 일어나서 랩실을 가서 풀었는데, 핵심적인 관찰이 재밌고, 그 결과까지의 과정이 재밌는 문제였다. 추천! Support Group에 사람이 포함되면 그 사람에 대응되는 정점을 선택한다고 하자. 관찰 1. 크기가 n인 clique가 있을 때, 그 clique에 포함되는 정점중 n-1개는 무조건 포함해야 한다. 관찰 1번은 나름 쉽게 떠올릴 수 있다. 우선 문제 지문에서부터 clique를 이용해야 하기에, 당연히 떠올릴 수 있고, 만약 n-2개 이하로 포함 한다면 포함되지 않는 새로운 clique가 생겨서 모순이다. 여기까지 생각한 후 생각의 전개는 다음과 같다. 1개만 교체할 수 있다면, 1개를 빼고 새로운 x개로 넣을 텐데, x가 1이라면 편하다.....

세상에서 제일 우울한 ucpc 후기는 넘어가도록 하고 기쁜 거 부터 써 보겠다... 최근 버츄얼 1번 + 본 대회 2번 5솔에 성공했다. E가 PBS라 쉽게 풀었다. 자세한 후기는 네이버 블로그에 있다. 혼자 버츄얼을 돌았다. E가 레이지 였는데 플2~1정도 기본 문제 급이라 쉽게 풀었다. 근데 정해는 아닌 것 같다... 내 풀이는 O(nlog^n)이었는데 터져서 상수 최적화 좀 하니까 뚫렸다. (long long ->int) 그리고 부캐가 2200에 도달했다..! E가 쉬운 small to large여서 바로 풀이가 보였다. 구현 미스땜에 2틀 + 30분정도 헤매다가 한 줄 고치고 바로 맞았다. 올해 목표 였던 2200을 달성해버렸다. 너무 일찍 달성해버려서 실감이 안나긴 하는데, 사실 div2는 의미..

2300 짜리 다익스트라 문제이다. https://codeforces.com/contest/1422/problem/D 풀이가 바로 보였는데 원트에 짜서 맞아서 기분이 좋았다. 일단 좌표 차이가 곧 cost인 다익스트라는 꽤 자주 나오는 유형이다. 나는 코포에서 예전에 쳐맞고 배웠는데, 즉 무슨 말이나면 abs(xi-xj)가 곧 cost인 다익스트라는 모든 정점 쌍에 대해 간선을 잇는게 아니라 x좌표가 가장 인접한 쌍에게만 간선을 이어주면 된다. 이 문제는 위 테크닉을 연습하기 좋은 문제라고 볼 수 있다. m개의 정점쌍들에 대해 x좌표 y좌표를 정렬한 후 살펴보면서 인접한 정점 쌍들에 대해서만 간선을 잇는 것이다. 그리고 다익스트라를 돌리고 나서 f와 각각의 정점 사이의 맨해튼 거리를 더해준 것 중 최소값..

문제를 요약하면, 수열에서 인접한 두 수를 골라 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..