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

scpc 166으로 망했다. 1번에 1시간을 썼다. 풀이는 보자마자 나왔는데 맞왜틀을 꽤 오래했다. 나머지는 그냥 골드만 긁었다 ㅎㅎ... 어제 결과가 나왔고 당연하게도 수상하지 못했다. 억울하다기 보다는 나 스스로에게 실망했고 화난다. 더 잘하고 싶다. suapc는 1등했다. sos dp를 내가 공부를 안 했었고, 우리 팀원들 중에 아는 사람이 없기도 했기에 이론상 맞출 수 있는 문제를 전부 맞춘 것 같다. lcp를 6개월 만에 짰는데 맞춘게 스스로 대견했다. 재밌게 풀었다. 자세한 후기는 Rebro님이 써주실 것으로 알고 있다 ㅎㅎ... 최근 1달동안 동기부여가 좀 덜 됐었는데, scpc를 망치고 나니까 갑자기 의욕이 막 생긴다. 더 잘하고 싶다. 화난다. 스스로에게 화나고 더 더 잘하고 싶다... ..

재밌고 교육적인 문제 ioi practice의 그래프 문제였다. 사실 함수구현이긴 하지만, interactive문제라고 보는 것이 더 정확할 것이다. 코포에 E번 정도에 나올법한 문제였다. i번 정점의 outdegree를 cnt[i]라고 하자. 우리는 모든 정점에 대해서, cnt[i]가 2이상인지를 확인해야 한다. 어떤 쿼리 query(x,y)를 날리게 되면, cnt[x]가 1 증가하던지, cnt[y]가 1 증가한다. 그렇다면 우리는 어떤 정점이 이미 cnt[i]가 2라면 굳이 이 정점을 이용한 쿼리를 날릴 필요가 없다는 점에 유의하자. interactor 가 adaptive이기 때문에 query(i,j)를 날리게 되면, cnt[i]를 interactor가 올리게 되면 확정적으로 아무 정보도 얻지 못한 ..

까먹기 전에 작성한다... 풀이를 안 보고 푼 문제가 거의 없다 ㅋㅋ. IOI는 진짜 너무 좋은 셋이다. 1. Antennas https://www.acmicpc.net/problem/25061 더보기 이 문제는 연습셋 도중에 풀이가 나왔었고, 정확히 정해랑 일치했는데, 시간이 없어서 셋 도중에 구현 못하기도 했고, 내 풀이에 자신이 없었다. 그냥 맞을거 같은데.. 까지는 나왔었는데, O(log n)번 이하로 작업이 이루어진다는 것을 증명하는 방법이 멋지니 꼭 알아두도록 하자. 증명 빼고는 나름? 웰노운 문제 2. 메기 농장 https://www.acmicpc.net/problem/25438 더보기 이 문제는 거의 접근 했고 풀이도 나왔는데, 핵심적인 관찰을 하지 못하면 구현이 매우 매우 더러워진다. 구..

교내 청정수컵 진행하다가 화났던 일인데 까먹었다가 방금 생각이 나서 다시 까먹지 않기 위해 적어봄 우리는 대회를 다산관에서 진행하기로 되어있었다. 한 3주전 부터 얘기를 해 놓은 상태고 학회원 한테 그렇게 공지해놓은 상태였는데 갑자기 사용불가능 하다는 연락이 왔다. 갑자기 거기서 다른 기업 코테를 친다네? ㅋㅋ 그래놓고 우리한테 변명으로 대회 자체가 서강대 전원 대상이 아니라 학회원 대상이기 때문에 안된다는 말도 안되는 변명을 자꾸 한다. 선약이 되어 있었으면 인간대 인간으로 이거는 우리한테 할당해야 하는게 당연히 맞지 않는가... 적게 참여하는 것도 아니고 100명 가까이 참여한 건데... 그냥 학교 차원에서 학생들 개무시하는게 느껴진다. 뭐 어쩌겠는가 우리가 을인데 학교에서 학회관련 일처리도 진짜 인..

재밌는 문제였다. 이 문제를 전날 자기 전부터 고민해서 일어나서 랩실을 가서 풀었는데, 핵심적인 관찰이 재밌고, 그 결과까지의 과정이 재밌는 문제였다. 추천! 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등등 여러가지.... )을 공부할 때 코드를 절대 보지 않는 것이 더 도움이 되는거 같다. 나는 대충 팀노트 복붙하면 되지 라는 마인드로 예전에 남의 코드를 베이스로 공부를 좀 했었는데 의미가 별로 없는 작업들인거 같다. 세그먼트 트리에 대해서 배운다고 가정을 하면,[구간을 로그 바운드로 쪼개서 관리한다] 라는 개념과 쿼리처리와 업데이트에 대해서 개념만 공부를 하고 구현하는 과정에 있어서는 혼자 힘으로 아무것도 보지 않고 직접 자기가 구현을 생각해서 타이핑 해보는게 더 도움이 되는거 같다. 물..