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

이 문제를 그래프로 해석해서 풀어보자. 각 학생은 다음 두 집합중에 하나에 속하게 된다. A = {우승가능성이 있는 학생} B = {어떻게 해도 항상 패배하는 학생} 우리의 목표는 A에 속한 학생들을 모두 구하는 것이 목적이다. 천적관계에 대해서 간선을 만든다고 생각해보자. 즉 x가 항상 y를 이긴다면 x->y인 모든 간선을 추가한다고 생각해보자. 첫번째 아이디어는 다음과 같다. A에 속해있는 임의의 정점을 a, B에 속해있는 임의의 정점을 b라고 해보자. 우선 연결그래프가 아닐 경우는 무조건 모든 정점이 되므로 넘어가자. (이건 쉬우니 생략하겠다...) 1. b에서 a로 가는 간선은 존재할 수 없다. 쉬운 증명: a는 이길 가능성이 있는데, a를 b가 이긴다는 것은 b도 이길 가능성이 있다는 뜻. 직관..

어제 있었던 라운드의 D번을 한번 풀어 보겠다. 어제는 셋이 매우 어려웠다. A,B,C,D모두 애드혹으로 발상이 힘들었다. 하지만 퀄리티 자체는 좋은듯... 어렵긴 해도... 풀이의 핵심은 절대 0이 될 수 없는 ai를 배제하자는 것에서 나온다. a,b,c 세 수가 있다고 하자. 그리고 gcd(a,b),gcd(a,c),gcd(b,c)를 알 때, 0이 될 수 없는 수를 어떻게 찾을까? 어떤 변수 x에 대해서 gcd(0,x)=x라는 사실을 이용하자. val[a]=gcd(a,b)+gcd(a,c) val[b]=gcd(b,a)+gcd(b,c) val[c]=gcd(c,a)+gcd(c,b) 라고 정의하자. 세 수 a,b,c중에 0이 존재한다면, val이 가장 큰 것이 0이된다. 그것도 strictly 하게 크다. 이..

더보기 이 문제는 3-coloring 문제와 연관시켜 푸는게 좋다. 즉 3-coloring보다 1-in-3 sat이 더 어렵다는 것을 보이면 (즉 1-in-3-sat을 풀 수 있다면 3-coloring 을 풀 수 있다는 것을 보이면 된다.) 3-coloring이 np complete임을 아므로, 자연스럽게 증명이 된다. 3-coloring문제를 다음과 같이 해석해보자. 각 정점 v에 대해서 v의 색깔 red,blue,green에 대한 세 변수 Rv,Bv,Gv를 만든다. 이 변수는 v가 red라면 Rv만 true이고, 나머지는 false이다. 모든 색에 대해 동일하게 적용된다. 그렇다면 (Rv or Bv or Gv)라는 clause를 각 v에 대해 만든다. 그 후 모든 edge (a,b)에 대해 다음과 같..

퀴즈가 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 더보기 이 문제는 거의 접근 했고 풀이도 나왔는데, 핵심적인 관찰을 하지 못하면 구현이 매우 매우 더러워진다. 구..