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

https://atcoder.jp/contests/abc278/tasks/abc278_g game 문제 누가 봐도 그런디를 쓰면 될 것 같다. 실제로 정해도 그런디 + 최적화 풀이를 언급. 하지만 실상은 애드혹 문제. 후공이 선공의 선택을 따라 할 수 있다는 것이 중요 포인트. https://codeforces.com/contest/1747/problem/E 그냥 dp 문제인데 중요한 점은 1차원에서 움직이는 걸 잘 합쳐서 2차원짜리 정답을 구하자. https://www.acmicpc.net/problem/22023 미친 문제. 최대 최소가 특정 값을 넘어가는 구간을 잘 찾으면 문제가 해결된다. 갓 문제. https://www.acmicpc.net/problem/25442 미친 문제2. 이분 탐색하는 거..

10000제출 달성. 백준 하지 마세요

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ... 아마 긴장해서 그런가 보다. E번 같은 유형은 내가 잘 못하는 유형이었는데 빠르게 F로 넘어갔다면 조금 더 침착해서 풀 지 않았을까... 일단 $s_c \leq n_c^2$ 라는 조건을 잘 해석해야 한다. 그런데 degree가 큰 정점 부터 살펴본다고 했을 때, x라는 정점에 degree(x)번 쿼리를 날린다고 하면, 우리는 (degree(x)+1)개의 정점으로 이루어진 connected component를 알게된다. 이들을 모두 같은 색으로 색칠하면 항상 조건을 만족한다. 왜나면, degree가 가장 큰 정점을 뽑았기 때문에 $s_c$는 degree(x)(degree(x)+1)이하이고, $n_c$는 (degree(x)+1)(degree(x)+1)이기 ..

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와 각각의 정점 사이의 맨해튼 거리를 더해준 것 중 최소값..