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

핵심은 홀 -> 홀/짝 으로 나누어 진다는 점이다. 즉 모두 홀수인 상태로 상대에게 넘겨주게 되면, 상대는 임의의 개수의 홀수를 다시 홀/짝으로 분해해서 줄 텐데, 홀수의 개수 >= 짝수의 개수 이다. 따라서 다시 항상 홀수인 상태로 상대에게 넘겨줄 수 있다. 따라서 내 차례에서 모든 짝수를 없앨 수 있다면 승리한다. 이에 생각을 확장해보면모두 홀수인 게임판은 후공이 이긴다.홀수와 짝수가 동시에 존재하는 게임판은 선공이 이긴다.짝수만 존재하면서 짝수가 짝수개인 게임판은 선공이 이긴다.결국 짝수만 있는, 짝수가 홀수개인 게임판이 문제가 된다.그런데 2번 상태 때문에, 홀수를 하나라도 넘겨주면 진다...따라서 이제 상대 차례에 모든 수를 짝수로 넘겨줄 수 있어야만 내가 이긴다.이 문제는 어떻게 풀까? 전체를..

뇌풀이인 이유는 시험기간이라 구현을 할 시간이 없기 때문이다...까먹기전에 여기에 기록한다.  https://www.acmicpc.net/problem/32484학회에서 예선 대비 팀 연습했을 때 만났던 문제이다. 아호코라식을 몰라서 실제 연습때는 던졌는데 롸선배의 풀이 세션에서 깨달음을 좀 얻어서 작성.여기서 S=10^6,N=10^5정도로 본다. 우선.... 이 문제는 여러 문자열 매칭을 하는 부분을 빼고 풀어보자.연결되는 부분들에 대해 간선을 이어서 유니온 파인드를 한다고 생각하면 동치임을 쉽게 알 수 있다.즉 같은 유파의 문자열들은 같은 횟수만큼 나왔어야 한다. 따라서 각 유파에 대해서, 가장 등장횟수가 많은 값 x, 등장횟수가 최대인 문자열의 개수 y, 그 유파의 크기 z를 관리하면항상 x==y이..

뇌풀이인 이유는 구현에 실패했기 때문이다.대략 140줄 정도 짜고 ide 껐다. 정해는 특수한 형태의 세그먼트 트리를 사용하면 풀 수 있다고 한다.문제를 분할정복으로 해결해보자. 각 분할하는 문제마다 결국 mid를 넘는 배열들에 대해서만 문제를 풀어주면 된다. 예제41 2 1 33 1 2 1로 문제를 설명해보면 이렇게 mid로 나눠버린다. 그러고 양쪽 방향으로 prefix max,min suffix max,min을 구한다. 그럼 문제는 이렇게 환원되는데 왼쪽 (Amax, Amin,Bmax,Bmin)원소와 오른쪽 (Amax,Amin,Bmax,Bmin)원소를 적절히 골라서 합쳤을 때,max=min이 되어야 한다. 물론 모든 쌍을 순회화면 O(n^2)이므로 빠르게 할 방법을 생각해봐야하는데,max의 suffi..

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

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

재밌고 교육적인 문제 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이라면 편하다.....

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

gold 에 있는 n binary search 불가 Q : 시작점을 고정시켰을 때 길이가 클 수록 좋은 구간의 값은 커지는가? A : 커진다. 그렇다면 다음 2가지 sub문제로 바꿔보자. 1. 특정 구간이 주어졌을 때 이 구간이 좋은 구간인지를 어떻게 판정할 것인가? 2. 좋은 구간이 주어졌을 때 이 구간의 값을 어떻게 판정할 것인가? 1번은 의외로 쉽게 할 수 있는데, 구간을 정렬하고, 앞에서 부터 합쳐주면서 홀 수 component가 되지 않으면 된다. 이 풀이의 정당성은 쉽게 증명 된다. 2번도 1번에서 파생되어 나온다. 합쳐나가면서 마지막으로 남는 수가 구간의 값이라는 것을 쉽게 알 수 있다. 그렇다면 본 문제를 풀어보자. 이제 핵심 아이디어는 1~39 까지 i를 순회하면서 i가 1일때는 연속된 ..