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

야심한 새벽에 만난 너무 좋은 문제 문제풀이는 크게 2가지로 나뉘어 진다. 1. 관찰 2. dp로 문제풀기 1번이 2번보다 조금 더 어려운거 같기는 하지만 2번도 쉽지는 않다. 일단 결론부터 말하면, k개의 연속한 문자가 한번이라도 등장한다면, 이 문자열은 항상 조건에 따라 만들 수 있다. 나는 이걸 종이에 몇개 써보면서 관찰에 성공했다. 증명은 꽤나 쉬운데, 우리는 k개의 연속된 substring을 골라서 같은 문자로 치환하는 작업을 반복할 것이다. 그러면 이건 순서가 있는 작업이기 때문에 마지막에 결과 string에서는 k개의 연속된 substring이 반드시 존재해야 한다. 그렇다면 k개의 연속된 substring이 존재하는 모든 string은 만들수 있을까? 만들 수 있다. 아이디어는 다음과 같다..

못풀고 에디토리얼 봤다. 보자마자 이거쓰면 풀리겠네 라고 바로 생각하게 되는 문제. https://codeforces.com/contest/1516/problem/D 풀이는 sparse table이다. 저 단어 하나만 떠올려도 문제를 풀 수 있다. sparse table문제를 진짜 오랜만에 만났는데, 복습해야 할 거 같다. dp도 유형이 많다. 곱이 lcm이라는건 결국 구간내의 모든 원소들이 서로소여야 한다. 그럼 투포인터로 dp[x][0]-> x번째 원소부터 출발했을때 갈 수 있는 최대 거리 로 정의를 하면 sparse table로 처리할 수 있고, 구간 쿼리를 logn에 처리할 수 있다. 처음에 보자마자 mo's로 잘짜면 되겠는데? 라는 생각을 했다. 이제 업데이트 없는 구간 쿼리는 스파스 테이블로 ..

강의용 + 복습용 리스트. 계속 추가 예정 https://atcoder.jp/contests/abc230/tasks/abc230_f https://codeforces.com/problemset/problem/1613/D https://codeforces.com/problemset/problem/1614/D2

정수론 문제다. 본대회때는 못풀었는데 똑같은 풀이를 "잘"구현하면 되는데 구현을 못해서 틀렸다. $f(n)=n*(n+1)/2$라고 하자. 고른 $k$개의 sequence $a_1$ ~ $a_k$의 합을 적절히 0으로 만들수 있다는 것은, $gcd(a_1,a_2,\cdots,a_k)$가 $f(a_1)+f(a_2)+\cdots f(a_k)$ 를 나눈다는 것과 정확히 동치이다. (옮긴 수를 옮기면 되므로) 그래서 우리는, gcd를 구해서 합을 나눌 수 있는지를 살펴보는 문제로 바뀌는데, 홀수가 있는 경우에는 항상 가능하다. 따라서 모든 수가 짝수인 부분 수열 중에 $gcd$가 $f(a_i)$합을 나누는지를 살펴보자. 그런데 $(n*(n+1)/2)=n/2$ (mod n) 이다. (n은 짝수이므로) 이거 진짜 멋..

2021 icpc 본선 문제. 다양한 풀이가 많은 것 같아서 내 풀이를 남기고자 한다. 문제요약. 정렬되지 않는 수열 A, B가 있다. 이때, A에서 딱하나 빼고, B에서 딱하나 빼자. 그리고 적절히 매칭했을때, 매칭된 모든 원소의 차이의 최댓값을 최소화하게 매칭됐을때 A에서 어떤 걸 빼는게 최적인가? 차이의 최댓값을 최소화를 동일하게 할 수 있다면, A중 값이 가장 작은걸 출력하라. 1. 빼는게 없다고 가정하면 정렬했을 때 매칭하는게 최적해다. 이건 well known 입니다. 증명은 넘기겠습니다. 2. 빼는게 있을 때 이런걸 생각해봅시다. 우선 정렬을 하고 matching을 합니다. 그런 상태에서 차이를 전부 계산해줍시다. 이때 최댓값을 dif라고 합시다. 최적으로 A,B를 하나씩 빼면 dif는 절대..

어제 2021 ICPC가 끝났고, 하고 싶은 이야기를 좀 해보려 한다. 정말 너무 떨려서 풀었어야 할 문제를 못푼거 같다. 19등을 했고, 아마 수상컷이 16~18정도일거 같아서 올해목표였던 수상은 못할거 같아 너무 아쉽다 ㅠㅠ gumgood 1bin 일단 수고하셨습니다! 타임라인을 저장해놓지는 않아서, AC받은 시간대 순서대로 작성하려 한다. 존댓말과 반말이 섞여서 써 있을 수 있다. 대회가 너무 어렵다고 생각이 들었는데, 스코어 보드에서 위에팀이 E,G를 전부 푼걸 보면서 좀 현타가 왔었다. 특히 E번은 지금보면 풀 거 같은데, 내가 잡고있을때 진짜 너무 멍을 때려 버렸다. Problem B Double Rainbow (11min +1) O(n^2)이 되기 때문에 실버 문제인데, 내가 잡았고 배열 초..

처음으로 div2 2자리수에 2000을 뚫었습니다. 부부캐가 본캐보다 높네요. orange에 가는 그날까지... keep going...

현재 시각 기준 15명에게밖에 풀려있지 않은 문제다. 매우 좋은 dp문제라는 생각이 들어서 풀이를 올린다. 1.배송비가 없다면 어떤 문제일까? mcmf의 기본형태이다. 2.배송비가 있을때 naive한 dp를 떠올려보자. 그렇게 되면 시간복잡도가 test case1개당 $O(NMS)$정도에 풀수 있고, 이는 너무 크다. (tc가 1개라면 적당히 최적화 할 여지가 존재한다.) 여기서 최적화를 잘하면 $O(NS)$정도에 줄일수도 있는데, 이렇게 해도, tc가 100개라 tle가 난다.(해보진 않음..ㅋㅋ!) 3.그리디한 전략 하나를 섞자. i번째 쇼핑몰에서 구매하기로 결정했으면, 그 쇼핑몰에서 항상 모든 물건을 구매하거나, 그 쇼핑몰이 마지막 쇼핑몰인 경우가 최적해이다. proof: 모든 물건을 구매하지 않은..

https://www.acmicpc.net/problem/22900 문제요약: 트리가 주어지고 간선에 가중치가 주어진다. 간선은 가중치가 존재할 때만 이용할 수 있다. 한번 움직일때마다 가중치를 원하는 만큼 뺀다. 움직일 수 없게 되는 사람이 지게 된다. 모든 시작위치에 대해서 선/후 공 중 누가 이기는지 구해라. 우선 가중치를 없애자. 어차피 모든 간선은 1번만 이용하는 걸로 생각해도 된다. (왜 그런지는 생각해보자.) 그럼 다음과 같은 tree dp형태로 바뀐다. 승리를 1, 패배를 0으로 칠한다면, 시작정점과 인접한 정점들 중에 0인 정점이 있다면 승리하고, 아니면 패배한다. 근데 모든 시작점에 대해 이걸 다 구하기는 어렵다. 그래프가 아니라 트리라는 걸 이용하자. 1번 정점을 루트로 잡고 dfs로..

1. x mod y =x - y (x/y) 2. 곱의 최소를 로그값들의 합의 최소로 바꿀 수 있다. 3. 놀랍게도 어떤 수의 자리수를 모두 곱한 값은 그 수 보다 작다. 4. 단조 감소/증가가 동일한 함수 끼리의 min/max 함수는 단조증감을 바꾸지 못한다. 5.http://mathman.kr/math/pita.htm 6.구조체를 만들어서 pq로 정렬할때 굉장히 큰 시간이 걸린다. 7.tree에서 모든 두 정점사이 단순경로 xor distance ---> 루트까지 xor이용해서 구하기. 8.부분구간은 구간합으로 생각해보기.(역으로 생각하기) 9.어떤 정수 a 가 있고 p와 서로소인 x를 생각하자. 그럼 a,a+x,a+2x,a+3x,.....a+(p-1)x 를 p로 나눈 나머지는 0~p-1을 전부 가진다..