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

퀴즈가 2문제가 나왔는데 증명까지 써서 제출해야 하는데 문제당 4분을 줬다; 족보가 없으면 불가능하다고 개인적으로 생각 ㅜㅜ. 둘 다 못 풀었다. 1. 그래프가 주어졌을 때, k개 이하의 clique들로 그래프를 분할 할 수 있는지 판단하는 것은 np complete임을 증명하라. 더보기 complement graph를 생각한다. 즉 간선들의 연결관계를 뒤집는다. 그렇다면 originial graph에서의 clique는 complement graph에서 independent 하다. 즉 complement graph에서 k-coloring 문제와 정확히 동치임을 알 수 있다. k-coloring은 k>=3에서 np-complete임을 아므로 끝. 2번 문제는 3-sat 어쩌구 였는데... 기억이 안나서 모..

자동장치 이론 기말고사 범위 책이다. 알고리즘 관련 내용이라 시간이 되면 교과서에 있는 예제를 풀어볼 생각이다..

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. 이분 탐색하는 거..

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ... 아마 긴장해서 그런가 보다. 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 더보기 이 문제는 거의 접근 했고 풀이도 나왔는데, 핵심적인 관찰을 하지 못하면 구현이 매우 매우 더러워진다. 구..

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

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값들..